Kombinationen einer Liste in Python

Verwenden Sie itertools.combinations(), um eine feste Anzahl von Elementen auszuwählen, ohne dieselbe Eingabeposition erneut zu verwenden. Wenn eine Position mehrmals ausgewählt werden darf, verwenden Sie itertools.combinations_with_replacement(). Beide Funktionen liefern Kombinationen, bei denen die Auswahlreihenfolge kein neues Ergebnis erzeugt; bei Permutationen gelten unterschiedliche Reihenfolgen als verschiedene Ergebnisse.

Die passende Kombinationsart auswählen

Wählen Sie mit combinations() eine feste Anzahl von Elementen aus, erlauben Sie mit combinations_with_replacement() die Wiederverwendung einer Position oder erzeugen Sie mit einer powerset()-Funktion alle Teilmengen. Die Funktionen der Standardbibliothek liefern Iteratoren mit Tupeln. Sie berücksichtigen die Positionen in der Eingabe. Daher können gleiche Werte an verschiedenen Positionen zu gleich aussehenden Tupeln führen. Die Reihenfolge der Ergebnisse richtet sich nach der Reihenfolge der Eingabepositionen; die Werte innerhalb der Tupel werden nicht automatisch sortiert. Für eine eigene Regel lässt sich der Auswahlvorgang mit Rekursion explizit umsetzen.

itertools.combinations() für Auswahlen ohne Wiederholung verwenden

itertools.combinations(iterable, r) liefert Tupel der Länge r, ohne eine Position erneut zu verwenden. Das Iterable wird in seiner Eingabereihenfolge verarbeitet. Wandeln Sie den Iterator in eine Liste um, wenn Sie alle Ergebnisse auf einmal speichern oder ansehen möchten; andernfalls können Sie direkt darüber iterieren.

Führen Sie dieses Beispiel aus:

Der Code und die angezeigten Bezeichnungen oder Ausgaben in diesem Abschnitt bleiben auf Englisch.

from itertools import combinations

items = ["red", "blue", "green"]
for pair in combinations(items, 2):
    print(pair)

Bei den Ergebnissen mit zwei Elementen wird jede Position höchstens einmal verwendet. Um einzelne Elemente anzufordern, setzen Sie r auf 1; für die gesamte Eingabe als ein Tupel setzen Sie r auf die Anzahl der Eingabepositionen. Ist r größer als die Anzahl der Positionen, enthält der Iterator keine Ergebnisse.

itertools.combinations_with_replacement() verwenden, wenn Auswahlen wiederholt werden dürfen

Verwenden Sie itertools.combinations_with_replacement(iterable, r), wenn dieselbe Eingabeposition mehrmals ausgewählt werden darf. Auch diese Funktion liefert Tupel der Länge r und folgt derselben positionsbasierten Reihenfolge. Bei der Auswahl von Paaren aus ["red", "blue"] gehören beispielsweise ("red", "red") und ("blue", "blue") dazu; combinations() würde diese Paare auslassen. Das ist nützlich, wenn eine wiederholte Auswahl sinnvoll ist, etwa wenn zwei Kugeln Eis denselben Geschmack haben dürfen. Das Argument r bestimmt weiterhin die Länge jedes Tupels.

Eine eigene Implementierung mit Rekursion oder einem Generator erstellen

Eine rekursive Backtracking-Funktion kann Ergebnisse in einer Liste sammeln. Bei jedem Schritt fügt sie einen Wert hinzu, ruft sich ab der nächsten Position erneut auf und entfernt den Wert anschließend wieder, damit die Schleife eine andere Auswahl ausprobieren kann. Ein Generator folgt derselben Auswahllogik, gibt aber jedes Ergebnis aus, sobald es gefunden wurde. Dadurch muss nicht die gesamte Ergebnismenge gespeichert werden, es sei denn, der Aufrufer wandelt sie ausdrücklich in eine Liste um. Das macht den Generator nicht grundsätzlich schneller.

Beide folgenden benutzerdefinierten Funktionen verlangen, dass r eine nicht negative Ganzzahl ist, und lösen andernfalls ValueError aus. Bei r = 0 liefert jede Funktion das einzelne leere Tupel; ist r positiv und größer als die Anzahl der Eingabepositionen, liefert keine der beiden ein Ergebnis. Der Generator prüft sein Argument erst, wenn die Iteration beginnt, da der Funktionskörper eines Generators verzögert ausgeführt wird.

Der Code und die angezeigten Bezeichnungen oder Ausgaben in diesem Abschnitt bleiben auf Englisch.

def get_combinations(items, r):
    if not isinstance(r, int) or isinstance(r, bool) or r < 0:
        raise ValueError("r must be a nonnegative integer")

    results = []

    def backtrack(start, chosen):
        if len(chosen) == r:
            results.append(tuple(chosen))
            return
        for index in range(start, len(items)):
            chosen.append(items[index])
            backtrack(index + 1, chosen)
            chosen.pop()

    backtrack(0, [])
    return results


def generate_combinations(items, r):
    if not isinstance(r, int) or isinstance(r, bool) or r < 0:
        raise ValueError("r must be a nonnegative integer")
    if r == 0:
        yield ()
        return
    for index in range(len(items)):
        for suffix in generate_combinations(items[index + 1 :], r - 1):
            yield (items[index],) + suffix


items = ["red", "blue", "green"]
print(get_combinations(items, 2))
print(list(generate_combinations(items, 2)))

Verwenden Sie für eine verzögerte eigene Variante yield, sobald eine vollständige Auswahl erreicht ist. Erhöhen Sie bei beiden Implementierungen den Index des nächsten rekursiven Aufrufs auf index + 1, damit keine Position wiederverwendet wird. Bei gleichen Eingabewerten können Ergebnisse gleich aussehen, obwohl sie von unterschiedlichen Positionen stammen.

Mit einer powerset()-Funktion alle Teilmengen erzeugen

Eine Potenzmenge enthält Teilmengen jeder Größe, darunter das leere Tupel und die vollständige Eingabe. Diese Implementierung verbindet die Ergebnisse für jede mögliche Größe. chain.from_iterable() liefert einen Iterator. Wandeln Sie ihn daher nur dann mit list() in eine Liste um, wenn alle Teilmengen materialisiert werden sollen.

Der Code und die angezeigten Bezeichnungen oder Ausgaben in diesem Abschnitt bleiben auf Englisch.

from itertools import chain, combinations


def powerset(items):
    values = list(items)
    return chain.from_iterable(
        combinations(values, size) for size in range(len(values) + 1)
    )


for subset in powerset(["red", "blue"]):
    print(subset)

Bei n Eingabepositionen umfasst eine Potenzmenge 2**n Teilmengen. Diese Anzahl wächst schnell. Verwenden Sie daher vorzugsweise einen Iterator für Kombinationen fester Größe, wenn die Aufgabe nur Auswahlen einer bestimmten Größe erfordert. Eine Potenzmenge eignet sich, wenn Ergebnisse aller Größen tatsächlich benötigt werden.