Kombinatorik in Python

Die Standard-Python-Bibliothek, die mit Version 2.2 beginnt, bietet viele Tools zum Generieren von kombinatorischen Objekten, aber ich konnte keinen einzigen Artikel im Internet finden, der ausführlich über die Arbeit mit ihnen berichtet. Deshalb habe ich mich entschlossen, dieses Versäumnis zu korrigieren.

Zunächst werde ich auf die Kombinatorik und ihre Grundformeln eingehen. Wenn Sie mit dieser mathematischen Sektion bereits vertraut sind, können Sie diese Absätze überspringen.

Angenommen, wir haben eine Zeichenfolge, die aus n verschiedenen Buchstaben besteht, und wir möchten alle Möglichkeiten berechnen, um diese Buchstaben so neu anzuordnen, dass eine neue Zeile entsteht. Für die erste Position in der Zeile können wir einen der n Buchstaben wählen, die wir haben, für die zweite Position einen der n- 1 Buchstaben und so weiter. Als Ergebnis erhalten wir das Produkt n (n-1) ... * 1 = n! die Anzahl der Permutationen von n Elementen ohne Wiederholung .

Stellen Sie sich nun vor, dass die Anzahl der Buchstaben in einer Zeichenfolge begrenzt ist. Wir haben n Buchstaben zur Verfügung und wollen berechnen, wie viele Möglichkeiten es gibt, aus ihnen eine Zeichenkette mit der Länge k zu bilden, wobei k <n ist und jeder Buchstabe nur einmal verwendet werden kann. Dann können wir einen von n Buchstaben an die erste Position in der Zeile, einen der n-1 Buchstaben an die zweite Position und einen der n-k + 1 Buchstaben an die k-te Position setzen. Die Gesamtzahl der Zeilen ist gleich n (n - 1) (n - 2) ... (n - k + 2) (n - k + 1) = n! / (Nk)! die Anzahl der Platzierungen von n bis k . Wenn die Eindeutigkeit der Buchstaben nicht erforderlich ist, erhalten wir die Formel n ... n n = n ^ k die Anzahl der Platzierungen von n bis k mit Wiederholungen .

Vorher haben wir die Sequenzen unter Berücksichtigung der Reihenfolge der Elemente sortiert, und was ist, wenn die Reihenfolge für uns keine Rolle spielt. Zum Beispiel haben wir n verschiedene Bonbons und wir möchten k davon auswählen, um sie einem Freund zu geben, und k <n. Wie viele Möglichkeiten gibt es, k Bonbons aus n ohne Rücksicht auf die Reihenfolge auszuwählen? Die Antwort ist einfach: Am Anfang finden wir eine Platzierung von n durch k ohne Wiederholung, aber dann werden die gleichen Mengen von Süßigkeiten mit unterschiedlicher Reihenfolge ihrer Reihenfolge wiederholt. Wie viele Möglichkeiten, k Bonbons neu anzuordnen? Das ist richtig, eine Permutation von k Elementen ohne Wiederholung. Die endgültige Antwort: Platzierungen von n durch k werden durch Permutationen von k ohne Wiederholungen geteilt. Formula $$$n! / (n-k)! / k!$die Anzahl der Kombinationen von n durch k .

Betrachten Sie den Fall als komplizierter, wir haben n Schachteln, von denen jede viele Süßigkeiten desselben Geschmacks enthält, aber in verschiedenen Schachteln sind die Geschmäcker unterschiedlich. Wie viele Möglichkeiten gibt es, einem Freund aus k Bonbons ein Geschenk zu machen, und wie oft kann der gleiche Geschmack vorkommen? Da die Bestellung für uns keine Rolle spielt, arrangieren wir die Geschenksüßigkeiten wie folgt: Am Anfang gibt es nacheinander Süßigkeiten des ersten Geschmacks, dann des zweiten und so weiter, und wir setzen Übereinstimmungen zwischen Süßigkeiten unterschiedlichen Geschmacks, wenn unser Geschenk keine Süßigkeiten jeden Geschmacks enthält. Streichhölzer, die links und rechts an diesen Geschmack grenzen sollten, werden nebeneinander stehen. Zusätzlich erhalten wir eine Sequenz bestehend aus k Süßigkeiten und n-1 Übereinstimmungen, da es nur n Geschmacksrichtungen gibt und Übereinstimmungen diese trennen. Beachten Sie nun, dass wir durch die Position der Übereinstimmungen den ursprünglichen Satz wiederherstellen können. Dann ist die Antwort die Anzahl der Möglichkeiten, eine n-1-Übereinstimmung in eine n + k-1-Zelle zu platzieren, ohne die Reihenfolge zu berücksichtigen, die der Anzahl der Kombinationen von n + k-1 durch n-1 entspricht. Die Formel lautet: $$$(n + k-1)! / k! / (n-1)!$die Anzahl der Kombinationen von n bis k mit Wiederholungen .

Um das Material zu konsolidieren, werden wir nun einige Probleme der Kombinatorik betrachten.

Aufgabe 1

Es gibt 20 Leute, wie viele Möglichkeiten gibt es, sie zu paaren
Lösung: Nehmen Sie die erste Person, wie viele Möglichkeiten es gibt, ein Paar für ihn zu wählen: $$$20-1 = 19$, nimm die zweite Person, wie viele Möglichkeiten es gibt, ein Paar für ihn zu wählen: $$$20-2-1 = 17$. Antwort: 19 !!! = 654729075

Aufgabe 2

Es gibt 10 Männer und 10 Mädchen, wie viele Möglichkeiten es gibt, sie in Unternehmen aufzuteilen, die aus der gleichen Anzahl von Männern und Mädchen bestehen. Eine leere Firma wird nicht berücksichtigt
Lösung:
Methode 1: Die Anzahl der Möglichkeiten, ein Unternehmen aus einem Mann und einem Mädchen zusammenzustellen, entspricht dem Produkt aus der Anzahl der Auswahlmöglichkeiten für ein Mädchen und der Anzahl der Auswahlmöglichkeiten für einen Mann. Die Anzahl der Möglichkeiten, ein Mädchen aus 10 auszuwählen, entspricht einer Kombination von 10 zu 1 ohne Wiederholung. Dies ist bei Männern ähnlich. Als nächstes berechnen wir auf ähnliche Weise die Kombinationen von 10 bis 2, von 10 bis 3 usw. bis zur Kombination von 10 bis 10. Die endgültige Formel: $$$(10! / (10-1)! / 1!) ^ 2 + (10! / (10-2)! / 2!) ^ 2 + ... + (10! / (10-10)! / 10!) ^ 2$.
Methode 2: Betrachten Sie die vielen Männer in der Firma und die vielen Mädchen, die nicht in ihrer Firma sind. Für diesen Satz können Sie die Firma definitiv wiederherstellen, und die Anzahl der Personen darin ist immer gleich 10, da $$$k + (10 - k) = 10$, k - die Anzahl der Männer in der Firma, $$$10 - k$- die Anzahl der Mädchen, die darin nicht enthalten sind. Die Anzahl solcher Sets entspricht der Anzahl der Kombinationen von 20 bis 10, in der endgültigen Antwort werden wir auch eins abziehen, um die leere Firma nicht zu berücksichtigen, wenn sich 10 Mädchen in unserem Set befinden. Die endgültige Formel: $$$20! / (20-10)! / 10! - 1 = 184755 US$.

Wir haben die Theorie herausgefunden und lernen nun, wie man kombinatorische Objekte mit der Standard-Python-Bibliothek erzeugt.
Wir werden mit der itertools- Bibliothek arbeiten

from itertools import * 

Mit der Permutationsfunktion können Sie alle Permutationen für ein iterierbares Objekt generieren.

Beispiel 1

 for i in permutations('abc'): print(i, end=' ') # abc acb bac bca cab cba print() for i in permutations('abb'): print(i, end=' ') # abb abb bab bba bab bba 

Basierend auf dem zweiten Aufruf stellen wir fest, dass dieselben Elemente an unterschiedlichen Positionen als unterschiedlich betrachtet werden.

Beispiel 2

 for i in permutations('abc', 2): print(i, end=' ') # ab ac ba bc ca cb 

Die Platzierung unterscheidet sich von der Permutation durch die Begrenzung der Anzahl verfügbarer Zellen

Beispiel 3

 for i in product('abc', repeat=2): print(i, end=' ') # aa ab ac ba bb bc ca cb cc 

Mit Wiederholungslayouts können Sie problemlos alle Zeichenfolgen mit fester Länge durchlaufen, die aus bestimmten Zeichen bestehen

Beispiel 4

 for i in combinations('abcd', 2): print(i, end=' ') # ab ac ad bc bd cd 

Wenn Sie Kombinationen ohne Wiederholungen verwenden, können Sie alle Sätze sich nicht wiederholender Buchstaben einer bestimmten Zeichenfolge, eines Arrays oder eines anderen iterierbaren Objekts unabhängig von der Reihenfolge durchlaufen

Beispiel 5

 for i in combinations_with_replacement('abcd', 2): print(i, end=' ') # aa ab ac ad bb bc bd cc cd dd 

Das Ergebnis ähnelt dem Aufrufen von Kombinationen , jedoch werden dem Ergebnis auch Mengen mit denselben Elementen hinzugefügt.

Material:
N.V. Gorbatschow "Sammlung von Olympiadenproblemen in der Mathematik"
Python-Dokumentation in russischer Sprache