Holen Sie sich alle möglichen (2^N) Kombinationen der Elemente einer Liste beliebiger Länge

Ich habe eine Liste mit 15 Nummern. Wie kann ich alle 32.768 Kombinationen dieser Zahlen erzeugen (dh eine beliebige Anzahl von Elementen in der ursprünglichen Reihenfolge)?

Ich dachte daran, die dezimalen Ganzzahlen 1–32768 zu durchlaufen und die binäre Darstellung jeder Zahl als Filter zu verwenden, um die entsprechenden Listenelemente auszuwählen. Gibt es einen besseren Weg, es zu tun?

_{Für Kombinationen einer bestimmten Länge, siehe Alle (n-choose-k)-Kombinationen der Länge n abrufen. Bitte verwenden Sie stattdessen diese Frage, um gegebenenfalls Duplikate zu schließen.}

_{Wenn Sie Fragen zur Kombinatorik als Duplikate schließen, ist es sehr wichtig, darauf zu achten, welches OP eigentlich will, nicht die Wörter, die verwendet wurden, um das Problem zu beschreiben. Es kommt sehr häufig vor, dass Personen, die beispielsweise ein kartesisches Produkt wünschen (siehe So erhalten Sie das kartesische Produkt mehrerer Listen), nach “Kombinationen” fragen.}

Schau mal rein itertools.combinations:

itertools.combinations(iterable, r)

Gibt Untersequenzen der Länge r von Elementen aus der iterierbaren Eingabe zurück.

Kombinationen werden in lexikografischer Sortierreihenfolge ausgegeben. Wenn also die Eingabe-Iterable sortiert ist, werden die Kombinationstupel in sortierter Reihenfolge erzeugt.

Seit 2.6 sind Batterien enthalten!

Hier ist ein fauler Einzeiler, der auch itertools verwendet:

from itertools import compress, product

def combinations(items):
    return ( set(compress(items,mask)) for mask in product(*[[0,1]]*len(items)) )
    # alternative:                      ...in product([0,1], repeat=len(items)) )

Hauptidee hinter dieser Antwort: Es gibt 2 ^ N Kombinationen – genau wie die Anzahl der binären Zeichenfolgen der Länge N. Für jede binäre Zeichenfolge wählen Sie alle Elemente aus, die einer “1” entsprechen.

items=abc * mask=###
 |
 V
000 -> 
001 ->   c
010 ->  b
011 ->  bc
100 -> a
101 -> a c
110 -> ab
111 -> abc

Dinge, die man beachten muss:

• Voraussetzung dafür ist, dass Sie anrufen können len(...) An items (Abhilfe: Wenn items ist so etwas wie ein Iterable wie ein Generator, wandeln Sie es zuerst in eine Liste um items=list(_itemsArg))
• Dies erfordert, dass die Reihenfolge der Iteration an items ist nicht zufällig (Workaround: sei nicht verrückt)
• Dies erfordert, dass die Artikel einzigartig sind, oder sonst {2,2,1} Und {2,1,1} werden beide zusammenbrechen {2,1} (Abhilfe: verwenden collections.Counter als Drop-In-Ersatz für set; Es ist im Grunde ein Multiset … obwohl Sie es möglicherweise später verwenden müssen tuple(sorted(Counter(...).elements())) wenn es hashbar sein soll)

Demo

>>> list(combinations(range(4)))
[set(), {3}, {2}, {2, 3}, {1}, {1, 3}, {1, 2}, {1, 2, 3}, {0}, {0, 3}, {0, 2}, {0, 2, 3}, {0, 1}, {0, 1, 3}, {0, 1, 2}, {0, 1, 2, 3}]

>>> list(combinations('abcd'))
[set(), {'d'}, {'c'}, {'c', 'd'}, {'b'}, {'b', 'd'}, {'c', 'b'}, {'c', 'b', 'd'}, {'a'}, {'a', 'd'}, {'a', 'c'}, {'a', 'c', 'd'}, {'a', 'b'}, {'a', 'b', 'd'}, {'a', 'c', 'b'}, {'a', 'c', 'b', 'd'}]

Dies ist ein Ansatz, der sich leicht auf alle Programmiersprachen übertragen lässt, die Rekursion unterstützen (keine Itertools, kein Yield, kein Listenverständnis):

def combs(a):
    if len(a) == 0:
        return [[]]
    cs = []
    for c in combs(a[1:]):
        cs += [c, c+[a[0]]]
    return cs

>>> combs([1,2,3,4,5])
[[], [1], [2], [2, 1], [3], [3, 1], [3, 2], ..., [5, 4, 3, 2, 1]]

Hier ist eine mit Rekursion:

>>> import copy
>>> def combinations(target,data):
...     for i in range(len(data)):
...         new_target = copy.copy(target)
...         new_data = copy.copy(data)
...         new_target.append(data[i])
...         new_data = data[i+1:]
...         print new_target
...         combinations(new_target,
...                      new_data)
...                      
... 
>>> target = []
>>> data = ['a','b','c','d']
>>> 
>>> combinations(target,data)
['a']
['a', 'b']
['a', 'b', 'c']
['a', 'b', 'c', 'd']
['a', 'b', 'd']
['a', 'c']
['a', 'c', 'd']
['a', 'd']
['b']
['b', 'c']
['b', 'c', 'd']
['b', 'd']
['c']
['c', 'd']
['d']