Sortierproblem in einem Baum

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

Montag 26. Mai 2008, 10:20

Hallo Leute,
ich versuche einen Baum Sequenziell abzuarbeiten und bekomme den irgendwie nicht sortiert. Ich hab mal ein Beispielbild von meinem Baum hochgeladen Bild
Er besteht als in dem Fall aus 9 verschiedenen Queries die ich wie schon gesagt habe sequenziell durcharbeiten will. Meine Idee war, fang mit den kürzesten an und gebe die Ergebnisse an den nächst längeren weiter.

Die Reihenfolge wäre dann
1 -> 9 -> 7 -> 8 -> 2 -> 6 -> 3 -> 4 -> 5
Um das hin zu bekommen hab ich mir mehrere Gedanken gemacht, unter anderem, welcher Knoten hat welche Kinder, wieviele Nachfahren und so weiter.

Hab dann mal eine Liste von Dictonarys zusammen gebaut, die die Information trägt, jetzt bekomme ich das aber nicht sortiert.

Code: Alles auswählen

list = [{'childs': [1, 2, 7, 9], 'offsprings': 7, 'parent': None, 'lig_in_cav': '90', 'cav_in_lig': '90', 'query_number': 0}, 
    {'query_number': 1, 'childs': [], 'offsprings': 0, 'parent': 0, 'level': '1'},
    {'query_number': 2, 'childs': [3, 6], 'offsprings': 4, 'parent': 0, 'level': '1'}, 
    {'query_number': 3, 'childs': [4, 5], 'offsprings': 2, 'parent': 2, 'level': '2'}, 
    {'query_number': 4, 'childs': [], 'offsprings': 0, 'parent': 3, 'level': '3'},
    {'query_number': 5, 'childs': [], 'offsprings': 0, 'parent': 3, 'level': '3'},
    {'query_number': 6, 'childs': [], 'offsprings': 0, 'parent': 2, 'level': '2'},
    {'query_number': 7, 'childs': [8], 'offsprings': 1, 'parent': 0, 'level': '1'}, 
    {'query_number': 8, 'childs': [], 'offsprings': 0, 'parent': 7, 'level': '2'},
    {'query_number': 9, 'childs': [], 'offsprings': 0, 'parent': 0, 'level': '1'}]
*ja, ich weiß, list ist ein schei.... Name aber ich hab den hier nur als Beispiel...*

Das sind die Infos die ich bis jetzt hab. Habe danach mit sortieren folgendes versucht:

Code: Alles auswählen

sortlist1 = sorted(list[:], key=lambda n: n.get('offsprings', '0'))
sort_query_list = sorted(sortlist1, key=lambda n: n.get('level', '0'))
dann habe ich aber letztendlich nur level 1 so sortiert wie ich es brauche, aber danach stimmt nichts mehr in der liste.

was ich jetzt versuchen wollte ist zu testen, ob kinder vorhanden sind, wenn diese vorhanden sind schauen wieviele nachfahren sie haben und dann eben in einer neuen liste die richtige reihenfolge zu speichern.

in meiner liste sind ja immer listen der kinder vorhanden und diese nr passt genau auf den index der list variablen, wenn man also querynr2 anschaut dann hat die in childs [3,6] was dann genau auf list[4] und list[6] passt.

ist denke ich zu verstehen, oder?

ich bekomme aber einfach diese funktion nicht an den sort befehl konzipiert... hat da jemand eine idee oder vielleicht eine bessere vorgehensweise?

ich müsste praktisch list[3]['offsprings'] mit list[6]['offsprings'] vergleichen
BlackJack

Montag 26. Mai 2008, 12:50

Ich würde sagen das wird mit einem `sort()` nicht zu machen sein. So ganz ist mir das Kriterium auch nicht klar, aber Deine Beispielreihenfolge bekommt man so hin:

Code: Alles auswählen

def iter_nodes(nodes):
    if not all(i == n['query_number'] for i, n in enumerate(nodes)):
        raise ValueError('query_number must match index')
    
    def rec_iter(node_index):
        node = nodes[node_index]
        children_indexes = sorted(node['children'],
                                  key=lambda n: len(nodes[n]['children']))
        for i in children_indexes:
            yield nodes[i]
            for subnode in rec_iter(i):
                yield subnode
    
    return rec_iter(0)
Mehrzahl von "child" ist übrigens "children".

Edit: Test auf notwendige Vorbedingung hinzu gefügt.
Zuletzt geändert von BlackJack am Montag 26. Mai 2008, 14:02, insgesamt 1-mal geändert.
würmchen
User
Beiträge: 255
Registriert: Mittwoch 7. November 2007, 14:17

Montag 26. Mai 2008, 12:50

Ok, ich hab jetzt einiges hinbekommen, und hab jetzt nur noch ein problem mit der Rekursion, das kann ich mir irgendwie nie so gut vorstellen...

das hab ich bis jetzt

Code: Alles auswählen

order = []
for i in list[0]['childs']:
    if len(list[i]['childs']) > 2:
        list[i]['childs'].sort(lambda x,y: cmp(list[x]['offsprings'],list[y]['offsprings']))
    order.append(list[i])
    for j in list[i]['childs']:
        order.append(list[j])
Problem ist hier, ich hab das nicht rekursiv gemacht, also er geht da nicht beliebig viele Ebenen tief in die Verschachtelung.

Das Ergebnis sieht dann so aus:

Code: Alles auswählen

{'query_number': 1, 'childs': [], 'offsprings': 0, 'parent': 0, 'level': '1'}
{'query_number': 9, 'childs': [], 'offsprings': 0, 'parent': 0, 'level': '1'}
{'query_number': 7, 'childs': [8], 'offsprings': 1, 'parent': 0, 'level': '1'}
{'query_number': 8, 'childs': [], 'offsprings': 0, 'parent': 7, 'level': '2'}
{'query_number': 2, 'childs': [6, 3], 'offsprings': 4, 'parent': 0, 'level': '1'}
{'query_number': 6, 'childs': [], 'offsprings': 0, 'parent': 2, 'level': '2'}
{'query_number': 3, 'childs': [4, 5], 'offsprings': 2, 'parent': 2, 'level': '2'}
Und es werden eben die Kinder der letzten query ausgelassen.

Kann mir da jemand erklären wie ich das Rekursiv umbaue? Sollte dann denke ich eine while Schleife sein mit der ich das letzte Element gleich dem Ausgangselement setze. Kann es mir aber gerade nicht zusammen bauen.
würmchen
User
Beiträge: 255
Registriert: Mittwoch 7. November 2007, 14:17

Montag 26. Mai 2008, 13:02

BlackJack hat geschrieben:Ich würde sagen das wird mit einem `sort()` nicht zu machen sein. So ganz ist mir das Kriterium auch nicht klar, aber Deine Beispielreihenfolge bekommt man so hin:

Code: Alles auswählen

def iter_nodes(nodes):
    def rec_iter(node_index):
        node = nodes[node_index]
        children_indexes = sorted(node['children'],
                                  key=lambda n: len(nodes[n]['children']))
        for i in children_indexes:
            yield nodes[i]
            for subnode in rec_iter(i):
                yield subnode
    return rec_iter(0)
Mehrzahl von "child" ist übrigens "children".
Hallo Black Jack, danke für Deine Hilfe, aber mir ist nicht ganz klar wie ich deine Funktion anwenden soll, verstehen tue ich sie auch nicht wirklich. Hab mit "yield" noch nichts zu tun gehabt. Beim anwenden gibt er mir jedenfalls ein Generatorobjekt zurück. Kannst Du mir vielleicht ein klein bisschen mehr erklären?
BlackJack

Montag 26. Mai 2008, 14:01

Die Funktion wird auf die Liste mit Deinen Dictionaries angewandt und liefert einen Generator, der wiederum die Dictionaries in der Reihenfolge liefert, die Du als Beispiel vorgegeben hast. Wenn Du's als Liste haben möchtest, einfach ``list(iter_nodes(nodes))`` verwenden.

Allerdings schaut sich die Funktion auch nur die Kinder jedes Knotens an und sortiert diese nach Blättern und inneren Knoten, bevor sie rekursiv besucht werden.

Das gibt, wie gesagt, die Reihenfolge, die Du als Beispiel angegeben hast, aber ich weiss nicht, ob Dir das letztendlich reicht, oder ob die Grösse des kompletten Unterbaums eines Knotens beim Sortieren eine Rolle spielen soll.
würmchen
User
Beiträge: 255
Registriert: Mittwoch 7. November 2007, 14:17

Montag 26. Mai 2008, 14:29

Ok, also die Funktion funktioniert nach meinen Vorstellungen, zumindest für dieses Beispiel, aber verstehen tue ich sie nicht.
Vielleicht kann sich hier nochmal jemand erbarmen und mir etwas dazu sagen...

die funktion rec_iter wird doch nie aufgerufen, oder doch? mir ist dieses vorgehen noch nicht ganz klar. Sie wird doch nur definiert.

wäre schön wenn das einer kommentieren würde
EyDu
User
Beiträge: 4871
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

Montag 26. Mai 2008, 14:41

Doch, rec_iter wird ganz am Ende in iter_nodes aufgerufen. Durchlaufe den Baum mit BlackJacks Code doch mal schrittweise per Hand. Am besten fängst du mit einem Baum der Größe 1 an und vergrößerst ihn dann langsam. Beim Verstehen und dann Anwenden von Rekursion wirst du um ein wenig Eigeninitiative wohl leider nicht rumkommen.
Antworten