Sortierproblem in einem Baum

[würmchen]

Hallo Leute,
ich versuche einen Baum Sequenziell abzuarbeiten und bekomme den irgendwie nicht sortiert. Ich hab mal ein Beispielbild von meinem Baum hochgeladen
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]

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.

[würmchen]

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]

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]

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]

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]

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.