Rekursion in liste Problem

[würmchen]

Hi Leute, ich hab ein Problem eine Liste rekursiv zu durchsuchen um bestimmte Index zurück zu bekommen. Ich versuch es mal zu beschreiben...

Zum einen Habe ich eine Liste die etwa so aussieht:

Code: Alles auswählen

a = [[1,7],[3],[],[],[6],[],[],[8,9],[],[],[]]

In dieser Liste sind Indizes gespeichert, die sich auf die gleiche Liste beziehen.

Mein Ziel ist es, für einen bestimmten Index immer eine liste mit den letzten Index zurück zu bekommen. zB. für index 4

Wenn ich für index 4 in der Liste oben schaue, dann steht da eine 6 drin. wenn ich danach für 6 in der Liste schaue, dann ist da eine leere Liste, also würde ich für den den Index 4 gerne eine Liste [6,] zurück bekommen.

Anderes Beispiel
Index 0
Ich schaue rein und finde 1 und 7, also schaue ich erst für 1 nach, hier steht eine 3, wenn ich bei 3 nachschaue ist wieder eine leere Liste und ich merke mir die 3, jetzt muss ich das ganze nochmal für die 7 machen und finde dort die 8 und die 9, die jeweils auf eine leere liste verweisen. Also hätte ich insgesamt eine Liste mit [3,8,9] bei der Suche nach Index 0.

Mein Problem ist genau an bei den Listen die größer als 1 sind. Hier weiß ich nicht wie ich bei der Rekursion die werte zurück geben soll, ohne dass ich den vorherigen überschreibe.

Kann mir da jemand helfen?

[nkoehring]

ehm... append und so, also ...ja Rekursion erklaert sich fuer mich nie einfach ^^

Die sich selbst aufrufende Funktion bekommt widerum eine leere Liste als Argument und kann dort dann immer fleißig die Ergebnisse speichern. Da Listen Zeiger sind, funktioniert es so auch mit der Rekursion.

[EyDu]

Vielleicht solltest du besser dein eigentliches Problem beschreiben und nicht einen Lösungsversuch. Dein Vorhaben hört sich schon irgendwie sehr seltsam an.

[str1442]

Code: Alles auswählen

>>> def f(ls, i):
...  return reduce(lambda a, b: a + [b] if not ls[b] else f(ls, b), ls[i], list())
... 
>>> a = [[1,7],[3],[],[],[6],[],[],[8,9],[],[],[]]
>>> f(a, 0)
[8, 9]

Irgendwie so, die 3 fehlt noch

Allerdings klingt so eine Struktur arg eigenartig.

EDIT: Klammer vergessen Geändert. Funktioniert jetzt.

Code: Alles auswählen

>>> def f(ls, i):
...  return reduce(lambda a, b: a + ([b] if not ls[b] else f(ls, b)), ls[i], list())
... 
>>> f(a, 0)
[3, 8, 9, 6]
>>> print a
[[1, 7], [3], [], [], [6], [], [], [8, 9, 4], [], [], []]

[CM]

Wenn ich für index 4 in der Liste oben schaue, dann steht da eine 6 drin. wenn ich danach für 6 in der Liste schaue, dann ist da eine leere Liste, also würde ich für den den Index 4 gerne eine Liste [6,] zurück bekommen.

Das geht *so* gar nicht:

Code: Alles auswählen

In [35]: a = [6,]
In [36]: a
Out[36]: [6]

Wenn ich Dich richtig verstehe, willst Du bei leeren Listen die Rekursion abbrechen lassen. Also an Deine "Rückgabeliste" einfach nichts dranhängen. Wenn da wirklich etwas stehen soll, könntest Du ein None dranhängen.

Mein Problem ist genau an bei den Listen die größer als 1 sind. Hier weiß ich nicht wie ich bei der Rekursion die werte zurück geben soll, ohne dass ich den vorherigen überschreibe.

Wenn Du per .append() Deine Liste verlängerst, überschreibst Du gar nicht. Wenn Du verhindern willst, dass Einträge doppelt vorkommen, einfach überprüfen, ob ein best. Index bereits in der "Rückgabeliste" vorkommt und dann ignorieren.

Reicht das als Tipp oder möchtest Du ein Beispiel?

Gruß,
Christian

[würmchen]

naja, das sind alles Listen von IDs die miteinander im Verhältnis stehen.

Im Prinzip sind es Objekte die eine Arbeit erledigen, diese Objekte haben Nachfahren, teilweise haben die mehrere Nachfahren usw.

Ich will mit meiner Abfragen herausfinden, von welchen Objekten ich die Ergebnisse einsammeln muss. Weil diese dann wiederum verknüpft werden müssen.

Objekt mit der ID 0 brauch dann die ergebnisse von 3,8,9

[EyDu]

Dann würde ich die Abhängigkeiten auch an die Objekte packen und nicht in eine Liste auslagern. Dann bekommen die Klassen noch eine entsprechende Methode um in den Eben abzusteigen und schon sieht das Problem viel leichter aus

[würmchen]

so hab ich es auch gemacht, wollte hier nur nicht alles reinstellen, weil ich es für "unwichtig" hielt, letztendlich greife ich ja nur auf die id's zu und auf eine variable in der die Abhängigkeiten stehen...

Wollte eine Art Minimalbeispiel liefern.

Ich denk ich hab es jetzt hinbekommen, vielleicht schaut noch jemand drüber ob ich irgendwas total falsch gemacht habe...

Code: Alles auswählen

def rek(l,i,e_list):
    for count,index in enumerate(i):
        if len(l[index]) >= 1:
            rek(l,l[index],e_list)
        else:
            e_list.append(index)

    return e_list

def main():
    a = [[1,7],[3],[],[],[6],[],[],[8,9],[],[10],[]]
    index = [0]

    test = []
    print rek(a,index,test)


if __name__ == "__main__":
    main()

EDIT: hab die Liste nochmal um einen Eintrag erweitert um zu überprüfen, wenn im Index 9 noch was drin steht, dass dann in der Finalen Liste nicht die 9 auftaucht, sondern dann eben wieder das letzte Element in dem Fall die 10....

[str1442]

Nachtrag: Meine Funktion funktioniert, habe Klammer vergessen, siehe oben.

Und deine funktioniert auch. Auch wenn du deinen IDs nicht den Namen index geben solltest (aber auch nicht id, das ist eine builtin Funktion). Und e_list würd ich bei Aufruf von rek wieder neu binden lassen, ansonsten funktioniert es nur wegen Seiteneffekten auf e_list, was ich als weniger schön empfinde.