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

Question

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

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

Input
{1,2,3}

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

Input
{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}} * 1 029 * {{2}, {1,2,3}}
{{3}, {1,2,2}}
{{1,2}, {2,3}} * * одна тысяча тридцать два {{1,3}, {2,2}}

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

Любая помощь приветствуется. Спасибо.

Answer 1

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

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

0 = 000 _b & rarr; ()
1 = 001 _b & rarr; (1)
2 = 010 _b & rarr; (2)
3 = 011 _b & rarr; (1, 2)
4 = 100 _b & rarr; (3) * * тысяча сорок две 5 = 101 _b & rarr; (1, 3)
6 = 110 _b & rarr; (2, 3)
7 = 111 _b & rarr; (1, 2, 3)

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

1 = 001 _b & rarr; (1) + (2, 3)
2 = 010 _b & rarr; (2) + (1, 3)
3 = 011 _b & rarr; (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)

Answer 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";
  }
}

Answer 3

Немного кода 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} в результирующем списке возвращает {{H, L1}, {L2}} и {{L1}, {H, L2}}

Answer 4

Я предлагаю ...

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

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

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

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

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

Я думаю, что sergdev использует очень похожий подход ко второму, но использует std :: map, а не hashtablestd :: unordered_map должно работать).Хеш-таблица должна быть быстрее для большого количества элементов, но не будет давать значения в каком-то определенном порядке.Порядок для каждого цикла в ключах в хеш-таблице должен быть согласованным, хотя , если вы не добавите / не удалите ключи.