Poniżej znajduje się „standardowa odpowiedź rekurencyjna”, podobna do innej podobnej odpowiedzi https://stackoverflow.com/a/23743696/711085 . (Nie musimy realistycznie martwić się brakiem miejsca na stosie, ponieważ nie ma możliwości przetworzenia wszystkich permutacji N!).
Odwiedza kolejno każdy element i albo go bierze, albo opuszcza (możemy bezpośrednio zobaczyć liczność 2 ^ N z tego algorytmu).
def combs(xs, i=0):
if i==len(xs):
yield ()
return
for c in combs(xs,i+1):
yield c
yield c+(xs[i],)
Próbny:
>>> list( combs(range(5)) )
[(), (0,), (1,), (1, 0), (2,), (2, 0), (2, 1), (2, 1, 0), (3,), (3, 0), (3, 1), (3, 1, 0), (3, 2), (3, 2, 0), (3, 2, 1), (3, 2, 1, 0), (4,), (4, 0), (4, 1), (4, 1, 0), (4, 2), (4, 2, 0), (4, 2, 1), (4, 2, 1, 0), (4, 3), (4, 3, 0), (4, 3, 1), (4, 3, 1, 0), (4, 3, 2), (4, 3, 2, 0), (4, 3, 2, 1), (4, 3, 2, 1, 0)]
>>> list(sorted( combs(range(5)), key=len))
[(),
(0,), (1,), (2,), (3,), (4,),
(1, 0), (2, 0), (2, 1), (3, 0), (3, 1), (3, 2), (4, 0), (4, 1), (4, 2), (4, 3),
(2, 1, 0), (3, 1, 0), (3, 2, 0), (3, 2, 1), (4, 1, 0), (4, 2, 0), (4, 2, 1), (4, 3, 0), (4, 3, 1), (4, 3, 2),
(3, 2, 1, 0), (4, 2, 1, 0), (4, 3, 1, 0), (4, 3, 2, 0), (4, 3, 2, 1),
(4, 3, 2, 1, 0)]
>>> len(set(combs(range(5))))
32