Разделить список списков на уникальные комбинации без перекрывающихся элементов

Question

У меня есть список списков, похожих на этот:

[[1, 2, 3], [2, 3, 4], [3, 5, 6]]

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

[
  [[1, 2, 3], [4], [5, 6]],
  [[1, 2], [4], [3, 5, 6]],
  [[1, 2], [3, 4], [5, 6]],
  [[1], [2, 3, 4], [5, 6]],
  [[1], [2, 4], [3, 5, 6]]
]

Можете ли вы указать мне самый питонский c способ сделать это?

Спасибо!

Answer 1

Существует канонический powerset рецепт

Я использую здесь модифицированную версию, которая не допускает пустое подмножество.

Затем мы объединяем все подмножества и фильтруем для тех, у кого нет дубликатов. Если вы хотите, чтобы все элементы, которые появляются в одном из первоначальных списков, использовались где-то, то функцию no_duplicates можно отредактировать, чтобы проверить это тоже.

from itertools import chain, combinations, product
from pprint import pprint

flatten = lambda l: [item for sublist in l for item in sublist]

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return list(chain.from_iterable(combinations(s, r) for r in range(1, len(s)+1)))

def no_duplicates(l):
    f = flatten(l)
    return len(set(f)) == len(f)

a = [[1, 2, 3], [2, 3, 4], [3, 5, 6]]

pprint(list(filter(no_duplicates, product(*list(powerset(x) for x in a)))))