Rekursion in liste Problem

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
würmchen
User
Beiträge: 255
Registriert: Mittwoch 7. November 2007, 14:17

Rekursion in liste Problem

Beitragvon würmchen » Montag 23. Februar 2009, 10:17

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?
Benutzeravatar
nkoehring
User
Beiträge: 543
Registriert: Mittwoch 7. Februar 2007, 17:37
Wohnort: naehe Halle/Saale
Kontaktdaten:

Beitragvon nkoehring » Montag 23. Februar 2009, 10:37

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
User
Beiträge: 4868
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

Beitragvon EyDu » Montag 23. Februar 2009, 10:58

Vielleicht solltest du besser dein eigentliches Problem beschreiben und nicht einen Lösungsversuch. Dein Vorhaben hört sich schon irgendwie sehr seltsam an.
Das Leben ist wie ein Tennisball.
Benutzeravatar
str1442
User
Beiträge: 520
Registriert: Samstag 31. Mai 2008, 21:13

Beitragvon str1442 » Montag 23. Februar 2009, 11:05

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 :D

Allerdings klingt so eine Struktur arg eigenartig.

EDIT: Klammer vergessen :idea: 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], [], [], []]
Zuletzt geändert von str1442 am Montag 23. Februar 2009, 11:16, insgesamt 2-mal geändert.
CM
User
Beiträge: 2464
Registriert: Sonntag 29. August 2004, 19:47
Kontaktdaten:

Re: Rekursion in liste Problem

Beitragvon CM » Montag 23. Februar 2009, 11:06

würmchen hat geschrieben: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.

würmchen hat geschrieben: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
User
Beiträge: 255
Registriert: Mittwoch 7. November 2007, 14:17

Beitragvon würmchen » Montag 23. Februar 2009, 11:09

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
User
Beiträge: 4868
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

Beitragvon EyDu » Montag 23. Februar 2009, 11:15

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 ;-)
Das Leben ist wie ein Tennisball.
würmchen
User
Beiträge: 255
Registriert: Mittwoch 7. November 2007, 14:17

Beitragvon würmchen » Montag 23. Februar 2009, 11:18

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....
Zuletzt geändert von würmchen am Montag 23. Februar 2009, 11:25, insgesamt 1-mal geändert.
Benutzeravatar
str1442
User
Beiträge: 520
Registriert: Samstag 31. Mai 2008, 21:13

Beitragvon str1442 » Montag 23. Februar 2009, 11:19

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.

Wer ist online?

Mitglieder in diesem Forum: jan.b