Maximum recursion depth

[MarcelF6]

Mittlerweile habe ich den Code ab dem if-Statement mit elif-Statements aufgefüllt.

max hab ich nun mal gelassen, weil ich der Meinung bin, dass es doch korrekt ist (für meinen Code).
Nun erhalte ich auch eine Ausgabe, die eigentlich alle korrekten Subsequenzen enthält. Leider aber auch solche, die keine sind. Das kommt daher, dass ich immer zwei miteinander vergleiche. Da mir aber noch keine Lösung eingefallen ist, wie ich das codemässig berücksichtigen soll, dass zuerst zwei verglichen werden sollen und dann das Ergebnis mit dem dritten String, stelle ich die Frage hier.

Ursprünglich habe ich einfach unter die elif-Statements noch einmal ein if-Statement gesetzt, also z.B.:

Code: Alles auswählen

elif xs[-1] == ys[-1]:
        if xs[-1] == zs[-1]:
            return subseq(xb, yb, zb) + [xs[-1]]

...aber mit dieser Variante kam ich zu keinem Ergebnis.

[jerch]

Die elif-Kaskade bringt nichts, dass Du da auch Dubletten findest ist doch klar, scliesslich testest Du auch auf diese.

Schau Dir lieber nochmal das max an, dort werden nämlich schonmal gefundene Lösungen wieder verworfen.

[jerch]

Vllt. fällt Dir das Problem mit dem max auf, wenn man Positionsangaben hinzufügt:

Code: Alles auswählen

def seq(a,b,c):
    len_x = len(a)
    len_y = len(b)
    len_z = len(c)
    f = lambda x,y,z: [] if not all((x,y,z)) else f(x[1:],y,z)+f(x,y[1:],z)+f(x,y,z[1:])\
        if not (x[0]==y[0]==z[0]) else (f(x[1:],y[1:],z[1:])+
        [(x[0], len_x-len(x),len_y-len(y),len_z-len(z))])
    return list(set(f(a,b,c)))

NB: Mit lambda bekommt man immer so schöne Einzeiler

[MarcelF6]

YES, finally
Vielen Dank für die Geduld und - vor allem - für das letzte Beispiel. Eigentlich hat mir erst das richtig die Augen geöffnet. ...der Code war eigentlich ganz ok - wenn ich dann gefundene Lösung nicht ignoriert (überschrieben) hätte...
Danke nochmals vielmals

[jerch]

@MarcelF6:
Ich weiss nicht, was eure Aufgabenstellung/Zielsetzung war, allerdings ist das Problem sehr ungünstig gelöst, da Deine Rekursionen unnötigerweise den Entscheidungsbaum mehrfach ablaufen (daher kommen auch die Dopplungen, die Du wieder filtern musst).

Edit:
Wenn es unbedingt Rekursion sein soll, hier mal ein anderer Vorschlag:

Code: Alles auswählen

def seq(*args):
    if len(args) == 1:
        return args[0]
    return seq(filter(lambda x: x in args[1], args[0]), *args[2:])

Die Funktion nimmt eine beliebige Anzahl von Strings/Iterables auf und konsumiert diese per Rekursion. Die Laufzeit sollte wesentlich besser sein als in Deinem Bsp.

Allerdings ist für diesen einfachen Anwendungsfall der Weg über sets, wie /me es gezeigt hat, allen eigenen Versuchen vorzuziehen. Sollte die Positionsangabe eine Rolle spielen, würde ich eher über ein Alphabetwörterbuch gehen:

Code: Alles auswählen

def seq(*args, **kwargs):
    hits = kwargs.get('hits')
    if not hits:
        hits = len(args)
    temp = {}
    for i,s in enumerate(args):
        for j,c in enumerate(s):
            item = temp.setdefault(c, [[] for _ in xrange(len(args))])
            item[i].append(j)
    return filter(lambda kv: len(filter(bool, kv[1]))==hits, temp.iteritems())

Über hits kann man dann auch andere Häufigkeiten abfragen.

[MarcelF6]

Danke für die weiteren Vorschläge.
Zum ersten Vorschlag habe ich eine Frage: So wie er hier steht gibt er am Schluss ja dann einfach die Wörter aus, oder?
Die eigentliche "Arbeit" für den Computer wäre dann ja trotzdem die Gleiche, weil er alle Buchstaben finden muss, die bei allen eingegeben Strings vorkommen...

Edit: Missverständnis korrigiert

[jerch]

Wer ist er?

@Arbeit:
Das Ergebnis sagt doch nichts über den Weg, über den Du das erreicht hast, aus.

[MarcelF6]

Naja, das stimmt schon. Aber falls ich den Algorithmus mit der Vorlage des ersten Vorschlags wieder gleich (d.h. analog) implementieren würde, wäre der PC trotzdem nicht schneller. (bzw. der Code an sich immernoch ungünstig).

[jerch]

Überleg Dir einfach mal, wie oft Dein Algorithmus die Stringelemente durchlaufen muss (das ist irgendwas exponentielles, O(3^(3*n)) worst case). Meine Version schafft es in O(n^3) für 3 Strings a n Elemente. Keine Frage, dass man das weiter verbessern kann, bleibt man allerdings beim Datentyp Liste, ist es kaum besser zu schaffen, da hier die Suche nunmal O(n) ist. Das Problem adressiert u.a. die Wörterbuchversion, wo man mit einer modifizierten Version es bis auf O(4*n) reduzieren könnte (unter der Annahme, dass der Zugriff O(1) average und die Alphabetlänge gleich der Stringlänge n ist).

Edit:
Falls Du nicht weisst, wovon ich hier rede, probier es einfach mal es mit unterschiedlicher Stringanzahl und Stringlängen.
Zum Schluss noch die vereinfachte Wörterbuchversion mit ein paar Erklärungen:

Code: Alles auswählen

def seq(*args, **kwargs):
    hits = kwargs.get('hits')
    if not hits:
        hits = len(args)
    temp = {}
    for s in args:                         # m Strings
        for c in s:                        # der Länge n (Vereinfachung): O(m*n)
            temp.setdefault(c, 0)          # O(1)
            temp[c] += 1                   # O(1)
    # return: temp enthält k Einträge                                   : O(m*n+k)
    # obere Abschätzung: k kann maximal n sein                          : O((m+1)*n)
    # Subaufrufe sind alle O(1) - keine Abhängigkeit zu m, n oder k
    return [k for k,v in temp.iteritems() if v==hits]

Mit der Counterklasse aus collections ginge der Quellcode noch weiter zu vereinfachen, allerdings sieht man dann die Einzelschritte für die Komplexitätsabschätzung nicht mehr.

Edit2: Unsinnige enumerates rausgenommen.