Получить все возможные комбинации из списка с дубликатами элементов?

Question

У меня есть список с повторяющимися элементами, например array = [2,2,2,7].

Если я использую решение, предложенное в этом ответе (используя itertools.combinations()), я получу:

()
(7,)
(2,)
(2,)
(2,)
(7, 2)
(7, 2)
(7, 2)
(2, 2)
(2, 2)
(2, 2)
(7, 2, 2)
(7, 2, 2)
(7, 2, 2)
(2, 2, 2)
(7, 2, 2, 2)

Как видите, некоторые «комбинации» повторяются, например, (7,2,2) появляется 3 раза.

Вывод, который я хотел бы получить:

()
(7,)
(2,)
(7, 2)
(2, 2)
(7, 2, 2)
(2, 2, 2)
(7, 2, 2, 2)

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

Answer 1

Вам потребуется сохранить набор кортежей, отсортированных по тому же принципу:

import itertools as it 

desired=set([(),(7,),(2,),(7, 2),(2, 2),(7, 2, 2),(2, 2, 2),(7, 2, 2, 2)])
result=set()
for i in range(len(array)+1):
    for combo in it.combinations(array, i):
        result.add(tuple(sorted(combo, reverse=True)))

>>> result==desired
True

Answer 2

Без использования itertools.combinations() и set:

from collections import Counter
import itertools

def powerset(bag):
    for v in itertools.product(*(range(r + 1) for r in bag.values())):
        yield Counter(zip(bag.keys(), v))

array = [2, 2, 2, 7]

for s in powerset(Counter(array)):
    # Convert `Counter` object back to a list
    s = list(itertools.chain.from_iterable(itertools.repeat(*mv) for mv in s))
    print(s)

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

---

Однако стоит отметить, что показанный выше метод будет медленнее, чем решения в других ответах, таких как этот , который просто группирует результаты из itertools.combinations() в set для удаления дубликатов, несмотря на будучи на первый взгляд менее эффективным, на практике это все же быстрее, поскольку итерации в Python намного медленнее, чем в C (см. itertoolsmodule.c для реализации itertools.combinations()).

Благодаря моему ограниченному тестированию, метод, показанный в этом ответе, превзойдет ранее цитированный метод, когда в вашем массиве приблизительно 14 различных элементов, каждый со средней кратностью 2 (в этот момент другой метод начинает отходить и выполняется во много раз медленнее), однако время работы любого из этих методов в этих обстоятельствах составляет> 30 секунд, поэтому, если производительность вызывает беспокойство, вы можете рассмотреть возможность реализации этой части вашего приложения на языке C.

Answer 3

Вы можете взять набор комбинаций и затем связать их вместе.

from itertools import chain, combinations

arr = [2, 2, 2, 7]

list(chain.from_iterable(set(combinations(arr, i)) for i in range(len(arr) + 1)))
# [(), (7,), (2,), (2, 7), (2, 2), (2, 2, 2), (2, 2, 7), (2, 2, 2, 7)]