Wie erhält man alle möglichen Kombinationen der Elemente einer Liste?

Question

Ich habe eine Liste mit 15 Zahlen, und ich muss einen Code schreiben, der alle 32.768 Kombinationen dieser Zahlen erzeugt.

Ich habe gefunden einige Codes (durch Googeln), die anscheinend tut, was ich suche, aber ich fand den Code ziemlich undurchsichtig und bin vorsichtig, es zu benutzen. Außerdem habe ich das Gefühl, dass es eine elegantere Lösung geben muss.

Das Einzige, was mir einfällt, wäre, einfach eine Schleife durch die Dezimalzahlen 1-32768 zu ziehen und diese in Binärzahlen umzuwandeln, und die Binärdarstellung als Filter zu verwenden, um die entsprechenden Zahlen herauszufiltern.

Kennt jemand einen besseren Weg? Verwendung von map() vielleicht?

Answer 1

Diese Antwort einen Aspekt übersehen: der OP fragte nach ALLEN Kombinationen... nicht nur nach Kombinationen der Länge "r".

Man müsste also entweder eine Schleife durch alle Längen "L" machen:

import itertools

stuff = [1, 2, 3]
for L in range(len(stuff) + 1):
    for subset in itertools.combinations(stuff, L):
        print(subset)

Oder - wenn Sie sich schick machen wollen (oder das Gehirn derjenigen, die Ihren Code nach Ihnen lesen, verbiegen wollen) - Sie können die Kette von "combinations()"-Generatoren erzeugen und diese durchlaufen:

from itertools import chain, combinations
def all_subsets(ss):
    return chain(*map(lambda x: combinations(ss, x), range(0, len(ss)+1)))

for subset in all_subsets(stuff):
    print(subset)

Answer 2

Werfen Sie einen Blick auf itertools.kombinationen :

itertools.combinations(iterable, r)

Gibt r lange Teilsequenzen von Elementen aus der Eingabe-Iterablen.

Die Kombinationen werden in lexikografischer Reihenfolge ausgegeben. Wenn also die Eingabe-Iterable sortiert ist, werden die Kombinations-Tupel in folgender Reihenfolge ausgegeben sortierter Reihenfolge erzeugt.

Seit 2.6 sind die Batterien im Lieferumfang enthalten!

Answer 3

Dieser Ansatz lässt sich leicht auf alle Programmiersprachen übertragen, 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]]

Answer 4

In den Kommentaren unter dem hochgestimmten Antwort von @Dan H., wird auf die powerset() Rezept in der itertools Dokumentation -einschließlich einer von Dan selbst . Allerdings Bisher hat noch niemand eine Antwort auf diese Frage gegeben. Da es wahrscheinlich einer der besseren, wenn nicht sogar der beste Ansatz für das Problem ist - und angesichts einer kleine Anregung von einem anderen Kommentator, sie ist unten abgebildet. Die Funktion erzeugt todos eindeutige Kombinationen der Listenelemente von cada Länge möglich (einschließlich derjenigen, die Null und alle Elemente enthalten).

Hinweis : Wenn das Ziel darin besteht, nur Kombinationen von eindeutigen Elementen zu erhalten, ändern Sie die Zeile s = list(iterable) zu s = list(set(iterable)) um alle doppelten Elemente zu entfernen. Unabhängig davon ist die Tatsache, dass die iterable wird schließlich in eine list bedeutet, dass es mit Generatoren funktioniert (im Gegensatz zu einigen der anderen Antworten).

from itertools import chain, combinations

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

stuff = [1, 2, 3]
for i, combo in enumerate(powerset(stuff), 1):
    print('combo #{}: {}'.format(i, combo))

出力します。

combo #1: ()
combo #2: (1,)
combo #3: (2,)
combo #4: (3,)
combo #5: (1, 2)
combo #6: (1, 3)
combo #7: (2, 3)
combo #8: (1, 2, 3)

Answer 5

Hier ist ein fauler Einzeiler, der ebenfalls 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)) )

Der Grundgedanke hinter dieser Antwort: Es gibt 2^N Kombinationen - das entspricht der Anzahl der binären Zeichenfolgen der Länge N. Für jede binäre Zeichenfolge werden alle Elemente ausgewählt, die einer "1" entsprechen.

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

Zu beachtende Punkte:

• Dies setzt voraus, dass Sie Folgendes aufrufen können len(...) auf items (Abhilfe: wenn items so etwas wie eine Iterable wie ein Generator ist, wandeln Sie sie zuerst in eine Liste um mit items=list(_itemsArg) )
• Dies erfordert, dass die Reihenfolge der Iteration auf items nicht zufällig ist (Abhilfe: nicht verrückt sein)
• Dies setzt voraus, dass die Gegenstände eindeutig sind, andernfalls {2,2,1} y {2,1,1} kollabieren beide zu {2,1} (Umgehung: Verwendung von collections.Counter als sofortiger Ersatz für set ; es ist im Grunde ein Multiset... obwohl Sie später vielleicht tuple(sorted(Counter(...).elements())) wenn Sie es als Hashwert benötigen)

---

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'}]