Wie ziehe ich bei Python k aus n Elementen so effizient wie möglich?
Gegeben ist eine Menge mit n unterschiedlichen Elementen. Man will nun alle möglichen Kombinationen (ohne Wiederholungen, ohne Reihenfolge) aus diesen Elementen mit k < n Elementen bilden. Davon gibt es laut Kombinatorik genau n über k.
Beispiel:
Gegeben: Menge M = {1, 2, 3, 4, 5}, n = 5, k = 3.
Gesucht: Alle Kombinationen aus M mit 3 Elementen: {{1, 2, 3}, {1, 2, 4}, {1, 2, 5}, {1, 3, 4}, {1, 3, 5}, {1, 4, 5}, {2, 3, 4}, {2, 3, 5}, {2, 4, 5}, {3, 4, 5}}.
Ob die Ausgabe eine Liste ist oder sonstiges ist egal. Wichtig ist folgendes: Ich muss diese Art von Mengen berechnen mit Zahlen wie zB n = 56 und k = 13. 56 über 13 ergibt 1,8 Billionen. Ich will zB, dass diese 1,8 Billionen Ergebnisse einzeln ausgegeben werden. Also nicht am Ende eine Liste, sondern 1,8 Billionen mal die einzelne geprintet. Ausserdem soll das ganze so effizient wie moeglich sein. Bisher habe ich eine Variante die so funktioniert:
from itertools import permutations
for indices in permutations(range(n), k):
if sorted(indices) == list(indices):
print(indices)
Das funktioniert, jedoch werden in der ersten For-Schleife alle Kombinationen berechnet mit Beachtung der Reihenfolge. Das ist VIEL zu ineffizient.
Kann mir jemand helfen?
1 Antwort
Dazu müsstest du dir ein Array basteln und dann die Elemente dieses Arrays gezielt
durcheinander mischen und einzeln ausgeben.
Beispiel:
3! = 1*2*3= 6:
abc, acb, bac, bca, cba, cab
Einfacher ist es jedoch dir zum Beispiel bei dir
Gegeben: Menge M = {1, 2, 3, 4, 5}, n = 5, k = 3.
eine Schleife basteln mit dem ersten Ausgabewert 100 und dem letzten 999.
Da ja k = 3
Da ja beide Limits für die Schleife 3 Stellen hat und du alle Möglichkeiten von 3er Kominationen ausgeben willst. Dazu wandelst du die Zahl in einen String und prüfst diesen auf Elemente, die du nicht haben willst. Etwa, das jedes Zeichen im String nur einmal vorkommen darf. Erst dann kannst du den String anzeigen.
In deinem einfachen Beispiel
wäre das in c
for (i = 100; i<= 999; i++)
{
//zuerst Zahl in String wandeln
//Dann prüfen ob jede Ziffer der Zahl nur einmal darin vorkommt
// Wenn letzte Bedingung erfüllt ist, String ausgeben
}
Da nur 123,132, 213,231,312 und 321 diese Vorgabe erfüllen, Zahl ausgeben.
Man kann zusätzlich dann auch ein eindimensionales Array mit Zeichen initialisieren 'a', 'b', 'c'
Dann zerlegst du die Ziffern wie etwa 312 wieder über den Umweg zum String in einzelne Ziffern, diese zu einem Zahlenwert und zeigst über eine separate Schleife
das Symbol dafür an.
Beide Vorgehensweisen kosten aber enorm viel Zeit.
Zudem ist im Normalfall nur ein Array aus Kleinbuchstaben, Großbuchstaben und Zahlen als Symbolische Platzhalter für die Elemente möglich:
26+26+10 = 62.
Aber 62 Faktorielle sind enorm viel.
Bis zur herkömmlichen Darstellung kannst du relativ einfach arbeiten,
da die Symbole für die Darstellung von dekadischen Ziffernsystemen auf 36
"0123456789abcdefghijklmnopqrstuvwxyz" begrenzt ist.
Solltest du etwa ein Passwort hacken wollen, bleibt dir nur der Weg mit der Schleife übrig. Eben weil eine ganz bestimmte Ziffernkombination einen bestimmten Zahlenwert aus einer Schleife zugeordnet werden kann.