Как сгенерировать список подмножеств с ограничениями?

StackOverflow https://stackoverflow.com/questions/1521589

  •  19-09-2019
  •  | 
  •  

Вопрос

Я пытаюсь выяснить эффективный алгоритм, чтобы взять список элементов и генерировать все уникальные подмножества, которые возникают в результате разделения списка на ровно 2 сублистов. Я уверен, что есть общий способ сделать это, но меня интересует конкретный случай. Мой список будет отсортирован, и могут быть дубликаты.

Некоторые примеры:

Вход
{1,2,3}

Выход
{{1},{2,3}}
{{2},{1,3}}
{{3},{1,2}}

Вход
{1,2,3,4}

Выход
{{1},{2,3,4}}
{{2},{1,3,4}}
{{3},{1,2,4}}
{{4},{1,2,3}}
{{1,2},{3,4}}
{{1,3},{2,4}}
{{1,4},{2,3}}

Вход
{1,2,2,3}

Выход
{{1},{2,2,3}}
{{2},{1,2,3}}
{{3},{1,2,2}}
{{1,2},{2,3}}
{{1,3},{2,2}}

Я могу сделать это на бумаге, но я изо всех сил пытаюсь найти простой способ сделать это программно. Я только ищу краткое описание псевдокода о том, как это сделать, а не какие -либо конкретные примеры кода.

Любая помощь ценится. Спасибо.

Это было полезно?

Решение

Следующая функция C ++ делает именно то, что вам нужно, но порядок отличается от той, которая в примерах:

// input contains all input number with duplicates allowed
void generate(std::vector<int> input) {
  typedef std::map<int,int> Map;
  std::map<int,int> mp;
  for (size_t i = 0; i < input.size(); ++i) {
    mp[input[i]]++;
  }

  std::vector<int> numbers;
  std::vector<int> mult;
  for (Map::iterator it = mp.begin(); it != mp.end(); ++it) {
    numbers.push_back(it->first);
    mult.push_back(it->second);
  }

  std::vector<int> cur(mult.size());
  for (;;) {
    size_t i = 0;
    while (i < cur.size() && cur[i] == mult[i]) cur[i++] = 0;
    if (i == cur.size()) break;
    cur[i]++;
    std::vector<int> list1, list2;
    for (size_t i = 0; i < cur.size(); ++i) {
      list1.insert(list1.end(), cur[i], numbers[i]);
      list2.insert(list2.end(), mult[i] - cur[i], numbers[i]);
    }
    if (list1.size() == 0 || list2.size() == 0) continue;
    if (list1 > list2) continue;
    std::cout << "{{";
    for (size_t i = 0; i < list1.size(); ++i) {
      if (i > 0) std::cout << ",";
      std::cout << list1[i];
    }
    std::cout << "},{";
    for (size_t i = 0; i < list2.size(); ++i) {
      if (i > 0) std::cout << ",";
      std::cout << list2[i];
    }
    std::cout << "}\n";
  }
}

Другие советы

Если бы вы генерировали все подмножества, вы бы в конечном итоге генерировали 2не Подмножества для списка длины не. Анкет Общий способ сделать это - итерация через все цифры я от 0 до 2не-1 и используйте биты, которые установлены я Чтобы определить, какие элементы находятся в яTh подмножество. Это работает, потому что любой элемент либо присутствует или нет в каком -либо конкретном подмножестве, поэтому путем итерации через все комбинации не кусочки вас перечитывают через 2не подмножества.

Например, чтобы генерировать подмножества (1, 2, 3) вы будете выполнять через числа от 0 до 7:

0 = 000беременный → ()
1 = 001беременный → (1)
2 = 010беременный → (2)
3 = 011беременный → (1, 2)
4 = 100беременный → (3)
5 = 101беременный → (1, 3)
6 = 110беременный → (2, 3)
7 = 111беременный → (1, 2, 3)

В вашей проблеме вы можете генерировать каждое подмножество и его дополнение, чтобы получить вашу пару взаимоисключающих подмножеств. Каждая пара будет повторена, когда вы это сделаете, поэтому вам нужно только выполнять итерацию до 2не-1 - 1, а затем остановись.

1 = 001беременный → (1) + (2, 3)
2 = 010беременный → (2) + (1, 3)
3 = 011беременный → (1, 2) + (3)

Чтобы справиться с дублирующими элементами, вы можете генерировать подмножества индексов списков вместо подмножествах элементов. Как и в списке (1, 2, 2, 3), генерируйте подмножества списка (0, 1, 2, 3) вместо этого, а затем используйте эти числа в качестве индексов в список (1, 2, 2, 3). Добавьте уровень косвенности, в основном.

Вот какой -то код Python, соединяющий все это вместе.

#!/usr/bin/env python

def split_subsets(items):
    subsets = set()

    for n in xrange(1, 2 ** len(items) / 2):
        # Use ith index if ith bit of n is set.
        l_indices = [i for i in xrange(0, len(items)) if n & (1 << i) != 0]
        # Use the indices NOT present in l_indices.
        r_indices = [i for i in xrange(0, len(items)) if i not in l_indices]

        # Get the items corresponding to the indices above.
        l = tuple(items[i] for i in l_indices)
        r = tuple(items[i] for i in r_indices)

        # Swap l and r if they are reversed.
        if (len(l), l) > (len(r), r):
            l, r = r, l

        subsets.add((l, r))

    # Sort the subset pairs so the left items are in ascending order.
    return sorted(subsets, key = lambda (l, r): (len(l), l))

for l, r in split_subsets([1, 2, 2, 3]):
    print l, r

Выход:

(1,) (2, 2, 3)
(2,) (1, 2, 3)
(3,) (1, 2, 2)
(1, 2) (2, 3)
(1, 3) (2, 2)

Немного кода Erlang, проблема в том, что он генерирует дубликаты, когда у вас дублирующие элементы, поэтому список результатов все еще необходимо отфильтровать ...

do([E,F]) -> [{[E], [F]}];
do([H|T]) -> lists:flatten([{[H], T}] ++
                           [[{[H|L1],L2},{L1, [H|L2]}]  || {L1,L2} <- all(T)]).

filtered(L) ->
  lists:usort([case length(L1) < length(L2) of true -> {L1,L2};
                                               false -> {L2,L1} end
              || {L1,L2} <- do(L)]).

В псевдокоде это означает, что:

  • Для двух длинного списка {e, f} результат {{e}, {f}}
  • Для более длинных списков возьмите первый элемент h и остальную часть списка T и возвращайте
    • {{H}, {t}} (первый элемент как один список элементов и оставшийся список)
    • Также запустите алгоритм рекурсивно для T, и для каждого элемента {L1, L2} в полученном списке return {{h, l1}, {l2}} и {{l1}, {h, l2}}}

Мое предложение ...

Во -первых, подсчитывайте, сколько у вас есть значения, возможно, в хэштере. Затем рассчитайте общее количество комбинаций, чтобы рассмотреть - продукт количества.

Итерация через это количество комбинаций.

В каждой комбинации скопируйте количество цикла (как x), затем запустите внутреннюю цикл через ваши хэштибильные элементы.

Для каждого элемента хэштета используйте (x Modulo Count) в качестве количества экземпляров хэштибельного ключа в первом списке. Разделите x на счет, прежде чем повторить внутреннюю петлю.

Если вы обеспокоены тем, что количество комбинаций может переполнить ваш целочисленный тип, проблема можно избежать. Используйте массив с каждым элементом (по одному для каждого ключа HashMap), начиная с нуля, и «считать» посредством комбинаций, рассматривающих каждый элемент массива как цифру (поэтому весь массив представляет собой комбинацию), но с каждой «цифрой», имеющей Разное основание (соответствующий счет). То есть, чтобы «увеличить» массив, первый элемент приращения 0. Если он переполняется (становится равным его количеству), установите его на ноль и увеличивает следующий элемент массива. Повторите проверку переполнения до тех пор, пока переполнение не продолжится после конца массива, вы закончили.

Я думаю, что Sergdev использует очень похожий подход к этому второму, но использует карту std :: map, а не хэштат (std :: unoromeded_map должен работать). Хештата должна быть быстрее для большого количества предметов, но не даст вам значения в любом конкретном порядке. Заказ для каждого цикла через ключи в хэштебе должен быть последовательным, хотя, пока не Вы добавляете/удаляете клавиши.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top