Permutationen mit Bedingung

Code-Stücke können hier veröffentlicht werden.
Antworten
Asharen
User
Beiträge: 2
Registriert: Sonntag 29. April 2018, 10:11

Ich versuche gerade aus einer "langen" Liste alle möglichen Permutationen zu generieren die eine bestimmte Bedingung erfüllen.
z.B. [A,B,C,D,E,F,G,.....X,Y,Z]. Bedingung z.B.: An erster Stelle muss immer A oder C stehen und an 3. Stellen X oder Z

1. Idee:
Verschachtelte Schleifen, d.h. eine Schleife für jedes Element in der Liste mit Abfrage der jeweiligen Bedingung.
Und ja, ich bin noch absoluter Anfänger :o aber die verschachtelten Schleifen kamen mir spontan als einfachste Lösung vor sofern die Liste nicht gerade 50+ Elemente hat.
Siehe da, Python kann anscheinend nur max. 20 Schleifen ineinander verschachteln.
Was also tun wenn die Liste mehr als 20 Elemente hat?

2. Idee:
mit Hilfe von itertools.permutations erstmal alle möglichen Permutationen erstellen.
Soweit ich das jetzt verstanden habe ist das Ergebnis von permutations() eine Liste mit Tupeln.
Im Anschluss jedes Tupel auf die Bedingung prüfen und ggf. entfernen.
Leider sprengt die Liste mit allen möglichen Permutationen den Arbeitsspeicher und es führt zu einem Memory Error.

Also bin ich auf der Suche nach einer Möglichkeit die Permutationen schon vorab über eine Bedingung zu prüfen.
Hat jemand eine Idee?
__deets__
User
Beiträge: 14493
Registriert: Mittwoch 14. Oktober 2015, 14:29

Dein zweiter Ansatz ist schon der richtige. Allerdings nutzt du offensichtlich nicht die Fähigkeiten von itertools bzw im allgemeinen Generatoren aus. Denn deren Vorteil liegt gerade darin, Daten zu erzeugen OHNE sie alle im Speicher halten zu müssen. Das klappt aber natürlich nur, wenn du die dann auch konsequent so weiter verarbeitest. Du zeigst keinen Code, darum kann man da nicht viel zu sagen. Aber das hier vielleicht als Startpunkt:

Code: Alles auswählen

def filtered_permutations(predicate, elements, length=None):
      for entry in itertools.permutations(elements, length):
            if predicate(entry):
                  yield entry
Der Schlüssel hier ist die Verwendung von yield, wodurch auch diese Funktion immer nur einen Wert konsumiert und produziert!

Man kann das auch gleich mit itertools.filterfalse machen, aber so siehst du die yield syntax.
Asharen
User
Beiträge: 2
Registriert: Sonntag 29. April 2018, 10:11

Danke ___deets___!
Genau das hat mir gefehlt.
Funktioniert wie es soll.
Zur Vervollständigung habe ich den Code angehängt.
Verbesserungsvorschläge, gerne :)


Code: Alles auswählen

from itertools import permutations
ergebnis = []
digits = [0,0,1,2,3,2,2,4,3,4,0,3]
gesamtanzahl = len(digits)
words_by_number = {
    0: ["AAA","BBB", "CCC"],
    1: ["DDD"],
    2: ["EEE", "FFF", "GGG"],
    3: ["HHH", "III", "JJJ"],
    4: ["KKK", "LLL"],
}

#Liste mit allen Wörtern erstellen:
list_words = []
for i in range(0,len(words_by_number)):
    list_words = list_words + words_by_number[i]

#Permutationen erstellen mit allen Wörtern als Funktion:
def permute(list_words,gesamtanzahl):
    for entry in permutations(list_words,gesamtanzahl):
        #Permutation prüfen auf Übereinstimmung mit digits:
        for index in range(0, gesamtanzahl):
            if entry[index] in words_by_number[digits[index]]:
                if index == gesamtanzahl-1:
                    #Ausgabe aktuelles Element des Generators:
                    yield entry
                else:
                    break

#Ausgaben der Funktion in Liste schreiben:
ergebnis = list(permute(list_words, gesamtanzahl))
#Listenelement in Datei ablegen:
with open("data/list.txt", "w") as file:
    for element in ergebnis:
        file.write(" ".join(element)+"\n")

#Ausgabe der Gesamtanzahl an validierten Ergebnissen:
print("Liste erstellt mit " + str(len(ergebnis)) + " Kombinationen")
Antworten