раздел набора или всех возможных подгрупп списка

Question

Предположим, у меня есть список [1,2,3,4] Я хочу создать все подмножества этого набора, которые будут охватывать все члены один раз, результат должен иметь 15 списки которых порядок не важен, а не т предоставляет все возможные подгруппы:

>>>>[[1,2,3,4]] 
[[1][2][3][4]] 
[[1,2],[3][4]] 
[[1,2],[3,4]] 
[[1][2],[3,4]] 
[[1,3],[2][4]] 
[[1,3],[2,4]] 
[[1][3],[2,4]] 
[[1],[2,3][4]] 
[[1,4],[2,3]] 
[[1][2,3,4]] 
[[2][1,3,4]] 
[[3][1,2,4]] 
[[4][1,2,3]] 

Это проблема набора разделов или partitions of a set который обсуждается here, но ответ заставил меня путать, как это только показывает, ссылаясь на перестановки, но Я не знаю, как! и another response также не включает [1,3] Тем временем я должен решить эту проблему для больших чисел, и результат должен обеспечить Bell Number Извините, я довольно новичок в python и запутался. Может ли кто-нибудь объяснить мне?

Answer 1

Вместо того чтобы делать все перестановки и удаления дубликатов, который был моей первой мыслью, то вы можете использовать эту рекурсивную функцию, которую я нашел here и here:

def partitions(set_): 
    if not set_: 
     yield [] 
     return 
    for i in range(int(2**len(set_)/2)): 
     parts = [set(), set()] 
     for item in set_: 
      parts[i&1].add(item) 
      i >>= 1 
     for b in partitions(parts[1]): 
      yield [parts[0]]+b 

l = [1, 2, 3, 4] 
for p in reversed(sorted(partitions(l))): 
    print(p) 
print('The Bell number is', len(list(partitions(l)))) 

Отпечатки:

[{1, 2, 3, 4}] 
[{1, 2, 4}, {3}] 
[{1, 4}, {2, 3}] 
[{1, 4}, {3}, {2}] 
[{2, 4}, {1, 3}] 
[{2, 4}, {3}, {1}] 
[{1, 3, 4}, {2}] 
[{2, 3, 4}, {1}] 
[{3, 4}, {1, 2}] 
[{3, 4}, {2}, {1}] 
[{4}, {1, 2, 3}] 
[{4}, {1, 3}, {2}] 
[{4}, {2, 3}, {1}] 
[{4}, {3}, {1, 2}] 
[{4}, {3}, {2}, {1}] 
The Bell number is 15 

Answer 2

from itertools import combinations 

s = [1, 2, 3, 4] 
for combs in (combinations(s, r) for r in range(len(s)+1)) : 
    for comb in combs: 
     print list(comb) 

ВЫВОД

[] 
[1] 
[2] 
[3] 
[4] 
[1, 2] 
[1, 3] 
[1, 4] 
[2, 3] 
[2, 4] 
[3, 4] 
[1, 2, 3] 
[1, 2, 4] 
[1, 3, 4] 
[2, 3, 4] 
[1, 2, 3, 4]