Das deutsche Python-Forum

Sirius3 hat geschrieben: Freitag 11. Oktober 2019, 14:54 Was meinst Du mit dem "immer" beim Löschen?

Wenn wir bis jetzt Backtracking gemacht haben, haben wir immer ein Element angefügt und es kurz darauf beim nächsten Aufruf wieder gelöscht

n-1 weil das nunmal das Wesen der Rekursion ist. Das ist wie ein induktiver Beweis. Du beziehst dich in Schritt n auf den Schritt n-1, und musst dann nur noch den Induktionsanfang bestimmen. Zumindest fuer dieses Problem passt das so.

Okay, also in magische Lösungen wird quasi schon der nächste Durchgang gemacht? Und du fängst ja dann bei z.b. n=4 an und verringerst dann in magische Lösungen n. Und magische Lösungen soll jetzt die Kombinationen, welche die Hauptfunktion sucht, mit dem regulären Ausdruck prüfen?

Haeh? Wo kommt denn jetzt der regulaere Ausdruck rein? Hier geht es doch einzig um ein kartesisches Produkt. So beschreibst du das zumindest oben. Was *danach* damit passiert, das steht auf nem anderen Blatt.

Achso, ich hab mich jetzt mit magische lösung durcheinander bringen lassen. Aber wenn doch die Funktion kartesisches_produkt schon über das Alphabet iteriert, was soll denn die magische Funktion noch zusätzlich machen?

Mein didaktischer Ansatz ist offensichtlich gescheitert. Magische Lösung ist auch nur das kartesische Produkt, nur eben mit einer Länge um eins reduziert. Man muss nur noch etwas im Fall n==0 anders machen. So funktioniert halt Rekursion. Offensichtlich lernt ihr aber eh vollkommen andere Techniken, mit diesem ganzen Modifizieren der Liste. Das musst du dir dann von wem auch immer sich das ausgedacht hat erklären lassen.

Dennoch vielen Dank für die Hilfsbereitschaft!

Ich wüßte nicht, wie man durch anhängen und wieder löschen eine rekursive Lösung bekommt. Das wo man sowas braucht ist ein Stack, und den benutzt man, wenn man von der rekursiven Lösung wegkommen will.

@__deets__: ich würde übrigens die Schleifen vertauschen, weil die teure Operation die Rekursion ist und die billige, alle Buchstaben durchzugehen:

Code: Alles auswählen

def kartesisches_produkt(alphabet, n):
    ergebnis = []
    for rest in kartesisches_produkt(alphabet, n-1):
        for buchstabe in alphabet:
            ergebnis.append(buchstabe + rest)
    return ergebnis

@Unplayable: und wenn man das durchspielt, wird kartesisches_produkt immer mit einem kleineren n aufgerufen. Induktionsanfang wäre, was passiert bei n == 1? Das soll Strings der Länge 1 mit von allen Buchstaben im Alphabet zurückliefern. Und diesen Sonderfall muß man noch einprogrammieren.

Sirius3 hat geschrieben: Freitag 11. Oktober 2019, 19:34 @__deets__: ich würde übrigens die Schleifen vertauschen, weil die teure Operation die Rekursion ist und die billige, alle Buchstaben durchzugehen:

Wo du recht hast, hast du recht!

Hallo nochmal,

vielen Dank euch beiden für die Hilfe!
Ich habe jetzt den Code von Sirius vervollständigt:

Code: Alles auswählen

def kartesisches_produkt(alphabet, n):
    ergebnis = []
    if n == 0:
        ergebnis.append("")
        return ergebnis
    if n == 1:
        for element in alphabet:
            ergebnis.append(element)
        return ergebnis
    for rest in kartesisches_produkt(alphabet, n-1):
        for buchstabe in alphabet:
            ergebnis.append(buchstabe + rest)
    return ergebnis

print(kartesisches_produkt(["a","b"], 2))

Da ich Angst hatte, dass ich es bis Montag nicht schaffe, habe ich es auch selbst weiter versucht und mich einfach mal an einer komplett iterativen Lösung versucht. (Einfach um etwas zu haben). Das Programm füllt mir meine Ergebnisliste auch korrekt auf, jedoch bin ich in einer Endlosschleife gefangen, und ich weiß nicht, wie ich da wieder raus komme.
Der Code sieht so aus:

Code: Alles auswählen

def kombinationen_aus_alphabet (startwert, endwert, alphabet, ergebnisliste):
    zaehler = 0
    if startwert == 0:
        ergebnisliste.append("")
     if zaehler == endwert:
        return ergebnisliste
    if len(ergebnisliste) <= 1:
        for element in alphabet:
            ergebnisliste.append(element)
            print(ergebnisliste)
    while zaehler != endwert:
        for wort in ergebnisliste:
            if wort != "":
                for element in alphabet:
                    ergebnisliste.append(wort + element)
                    zaehler += 1
                    print(ergebnisliste)
                    print(zaehler)
                    break
                    
        print(ergebnisliste)
        print(zaehler)

            
    
print(kombinationen_aus_alphabet (0,4,["a","b"],[]))

EDIT:

Ich habe wohl die ganze Zeit einfach viel zu kompliziert gedacht. Das Beispiel von Sirius sind ja nun wirklich nur ein paar Zeilen Code und ich hab mir so schwer damit getan. Vermutlich muss man die Prozedur einfach ein Mal richtig verstanden haben. Ihr habt mir wirklich geholfen!

Gerade bei Deiner interaktiven Lösung ist es Quatsch, die Ergebnisliste als Parameter zu übergeben, weil ja das gesamte Ergebnis in einem Funktionsdurchlauf erzeugt wird. Wann zaehler innerhalb der while-Schleife hochgezählt wird ist absolut undurchsichtig. Und die innerste for-Schleife wird nach dem ersten Durchlauf immer per break abgebrochen, ist demnach also gar keine Schleife.

Okay, ich habe die Ergebnisliste jetzt als lokale Variable mit [] gesetzt. Aber wieso verlässt das Programm die while-Schleife denn nicht? Ich habe doch als Bedingung angegeben, dass zaehler ungleich dem Endwert sein muss. Und wenn ich mir den zaehler jeweils mit Print ausgeben lasse, dann steigt er weit über den Endwert. Habe ich jetzt etwas vergessen oder passt die Folge der Schleifen einfach nicht?

Wo und wie wird den zaehler erhöht? Was hast Du Dir für Gedanken gemacht das an der Stelle zu tun? Was wäre ein aussagekräftiger Name statt zaehler damit klarer wird, was da gezählt wird?

Meine Idee war, dass ich den Zähler, welcher von 0 bis zum Endwert hochzählt (deshalb eben Zähler) nachdem ich jeden Buchstaben an alle bisher erstellten Kombinationen angehängt habe, um 1 erhöhe (+=1), damit ich im nächsten Aufruf Wörter mit der Länge +1 erstellen kann (ähnlich wie bei der Rekursion)

Und wann zählst Du?

Ich wollte dann zählen, wenn ich jedem Wort, welches bis jetzt in der Ergebnisliste ist, jedes Element angehängt habe. Theoretisch müsste ich ja dann das Zählen auf Höhe von der ersten for-Schleife stellen. Aber wenn ich es dorthin packe, dann bleibt zaehler immer auf 0

Spasseshalber mal eine praxisnähere Lösung in Python, unter Verwendung der Werkzeuge, die man über die Standardbibliothek schon an die Hand bekommt:

Code: Alles auswählen

#!/usr/bin/env python3
from itertools import product


def create_product(alphabet, start_length, end_length):
    for length in range(start_length, end_length + 1):
        yield from map("".join, product(alphabet, repeat=length))


def main():
    print(list(create_product("ab", 1, 2)))


if __name__ == "__main__":
    main()

Auch hierfür danke

Das deutsche Python-Forum

Regulären Ausdruck in Python prüfen

Re: Regulären Ausdruck in Python prüfen

Re: Regulären Ausdruck in Python prüfen

Re: Regulären Ausdruck in Python prüfen

Re: Regulären Ausdruck in Python prüfen

Re: Regulären Ausdruck in Python prüfen

Re: Regulären Ausdruck in Python prüfen

Re: Regulären Ausdruck in Python prüfen

Re: Regulären Ausdruck in Python prüfen

Re: Regulären Ausdruck in Python prüfen

Re: Regulären Ausdruck in Python prüfen

Re: Regulären Ausdruck in Python prüfen

Re: Regulären Ausdruck in Python prüfen

Re: Regulären Ausdruck in Python prüfen

Re: Regulären Ausdruck in Python prüfen

Re: Regulären Ausdruck in Python prüfen

Re: Regulären Ausdruck in Python prüfen

Re: Regulären Ausdruck in Python prüfen

Re: Regulären Ausdruck in Python prüfen