Как сгенерировать список подмножеств с ограничениями?
-
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 должен работать). Хештата должна быть быстрее для большого количества предметов, но не даст вам значения в любом конкретном порядке. Заказ для каждого цикла через ключи в хэштебе должен быть последовательным, хотя, пока не Вы добавляете/удаляете клавиши.