Выбор неупорядоченных комбинаций из пулов с перекрытием ⇐ Python

[Anonymous]

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

Например, я хотел выбрать из пула 0, пул 0 и пул 1:

Код: Выделить всё

>>> pools = [[1, 2, 3], [2, 3, 4], [3, 4, 5]]
>>> part = (0, 0, 1)
>>> list(product(*(pools[i] for i in part)))
[(1, 1, 2), (1, 1, 3), (1, 1, 4), (1, 2, 2), (1, 2, 3), (1, 2, 4), (1, 3, 2), (1, 3, 3), (1, 3, 4), (2, 1, 2), (2, 1, 3), (2, 1, 4), (2, 2, 2), (2, 2, 3), (2, 2, 4), (2, 3, 2), (2, 3, 3), (2, 3, 4), (3, 1, 2), (3, 1, 3), (3, 1, 4), (3, 2, 2), (3, 2, 3), (3, 2, 4), (3, 3, 2), (3, 3, 3), (3, 3, 4)]

При этом создаются все возможные комбинации путем выбора из пула 0, пула 0 и пула 1.

Однако порядок для меня это не имеет значения, поэтому многие комбинации на самом деле являются дубликатами. Например, поскольку я использовал декартово произведение, генерируются оба числа (1, 2, 4) и (2, 1, 4).

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

Код: Выделить всё

cnt = Counter()
for ind in part: cnt[ind] += 1
blocks = [combinations_with_replacement(pools[i], cnt[i]) for i in cnt]
return [list(chain(*combo)) for combo in product(*blocks)]

Это уменьшает количество дубликатов, если мне приходится выбирать из одного и того же пула несколько раз. Однако все пулы во многом перекрываются, и использование groups_with_replacement при объединении нескольких пулов приведет к созданию некоторых недопустимых комбинаций. Есть ли более эффективный метод создания неупорядоченных комбинаций?

Изменить: Дополнительная информация о входных данных: количество частей и пулов невелико (~ 5 и ~ 20), и для простоты каждый элемент является целым числом. Реальную проблему я уже решил, так что это просто ради академического интереса. Допустим, в каждом пуле тысячи сотен целых чисел, но некоторые пулы малы и содержат только десятки. Таким образом, кажется, что какой-то союз или пересечение — это путь.

Подробнее здесь: https://stackoverflow.com/questions/518 ... th-overlap