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

Question

Итак, у меня есть несколько наборов:

sets = [
   {a1,a2}, #a set
   {b1,b2}, #b set
   {c1,c2}, #c set
   ...
]

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

[
   {a1}, {b1}, ...,                        # all single
   {a1, b1}, {a1, b2} ...,                 # all pairs
   ...                                     # all combinations less than n
   {a1,b1,c1 ... }, {a2,b1,c1 ... }, ...,  # size n
]

В в тот момент, когда я использую powerset iter_tools для объединения всех наборов, а затем фильтрации, но это невероятно медленно, когда наборы становятся большими.

large_set = union_all_sets(sets)
r = more_itertools.powerset(large_set)
r = filter_1(r)

Мне было интересно, есть ли простая функция для этого, которая Я не знаю имя? Или, если у кого-нибудь есть предложения, как мне избежать вызова powerset на большом наборе?

Answer 1

Вы можете построить комбинации из 1, затем 2 ... n ваших наборов, и для каждой из этих комбинаций сгенерировать декартово произведение:

from itertools import product, combinations

sets = [
   {"a1", "a2"}, #a set
   {"b1", "b2"}, #b set
   {"c1", "c2", "c3"} #c set
]

out = []

for size in range(1, len(sets)+1):
    for combination in combinations(sets, r=size):
        out.extend(set(p) for p in product(*combination))

print(out)

Выход:

[{'a2'}, {'a1'}, {'b1'}, {'b2'}, {'c2'}, {'c1'}, {'c3'}, 
 {'b1', 'a2'}, {'b2', 'a2'}, {'b1', 'a1'}, {'b2', 'a1'}, {'c2', 'a2'},
 {'c1', 'a2'}, {'c3', 'a2'}, {'c2', 'a1'}, {'c1', 'a1'}, {'c3', 'a1'}, 
 {'b1', 'c2'}, {'b1', 'c1'}, {'b1', 'c3'}, {'c2', 'b2'}, {'c1', 'b2'}, 
 {'b2', 'c3'}, 
 {'b1', 'c2', 'a2'}, {'b1', 'c1', 'a2'}, {'b1', 'c3', 'a2'}, {'c2', 'b2', 'a2'}, 
 {'c1', 'b2', 'a2'}, {'b2', 'c3', 'a2'}, {'b1', 'c2', 'a1'}, {'b1', 'c1', 'a1'}, 
 {'b1', 'c3', 'a1'}, {'c2', 'b2', 'a1'}, {'c1', 'b2', 'a1'}, {'b2', 'c3', 'a1'}]