Listen von Listen nach multiplen Kriterien sortieren: aehnliche Werte gleich behandeln

[stillsen]

Hi,
ich moechte eine Liste von Listen nach mehreren Kriterien sortieren, so dass aehnliche Werte als gleich behandelt werden.
Genauer.
Es gibt eine Liste mit bis zu 12 Listen a 3 Werte (x, y, r).

Code: Alles auswählen

 
 circles = [[536, 565, 326], [2132,  578,  323], [1296,  590,  321], [2108, 1408,  326], [ 509, 1418,  324], [1290, 1450,  324], [2134, 2269,  321], [1320, 2300,  323], [ 534, 2320,  318], [2138, 3137,  318], [ 485, 3145,  321], [1331, 3145,  326]]
 

Ich moechte die Liste als erstes Kriterium nach y und zweitens nach x sortieren.
Soweit so gut.

Code: Alles auswählen

circles.sort(key = lambda x: (x[1],x[0]))

Das Problem was ich habe ist, dass fuer jeweils 3 Unterlisten der y Wert nicht identisch aber aehnlich ist, jedoch fuer die Sortierung aehnliche y Werte als identische behandelt werden sollen, so dass bei diesen, nach dem zweiten Kriterium sortiert wird.
1) sortiere nach ~ y
2) sortiere nach x

Also sowas rauskommt:

Code: Alles auswählen

[ x, y, r]

[536, 565, 326], 
[1296, 590, 321], 
[2132, 578, 323], 
[509, 1418, 324], 
[1290, 1450, 324], 
[2108, 1408, 326]

Meine urspruengliche Idee war es, die Liste erst nach y zu sortieren und dann eine Teilliste nach x zu sortieren.

Code: Alles auswählen

circles[0:3].sort(key = lambda x: x[0])

Nur scheint das keinen Effekt zu haben.

Hat jemand eine Idee, wie ich die Liste als erstes Kriterium nach aehnlichen y Werten sortieren kann und als zweites nach x Werten?

Danke schonmal fuer die Hilfe!

[/me]

Zunächst mal solltest du festlegen, was du als "ähnlich" definierst.

Sind bei den Werten 120, 190, 210, 280 die ähnlichen Werte (120, 190) und (210. 280) oder sind es die drei Gruppen (120), (190, 210) und (280)?

[Sirius3]

Erster Schritt ist eine Definition der Ähnlichkeit, dann eine Funktion, die Zahlen in Ähnlichkeitsgruppen einsortiert, und dann kannst Du nach diesen Ähnlichkeitsgruppen sortieren.
Ja nach Definition kann das auch eine einfache Funktion sein, die nur die Zahl als Input und die Gruppierung als Output hat, so dass die Sortierung als sort(key=lambda x:(ähnlich(x[1]), x[0])) geschrieben werden könnte.

[stillsen]

wenn ich die aeussere Liste sortiere mit

Code: Alles auswählen

circles.sort(key = lambda x: x[1])

dann sind die y Werte von drei aufeinander folgenden Unterlisten aehnlich, z.B. (565, 590, 578) bei den ersten dreien oder (1418, 1450, 1408) bei den darauf folgenden, usw..
Bezeichnen wir diese drei aufeinander folgenden aenhlichen y-Werte als Gruppe, dann wuerde ich aehnlich definieren als Abweichung vom Gruppendurchschnitt innerhalb eines Limits (z.B. 50).

danke fuer den Hinsweis, dass ich in der Lambdafunktion eine Aenhlichkeitsfunktion benutzen kann. Probiere ich nachher gleich mal aus

[Sirius3]

Wenn Du die Ähnlichkeit am Mittelwert der Gruppe festmachst, ist es natürlich nicht möglich, das direkt zu berechnen. Solch ein Kriterium ist relativ schwierig umzusetzen. Was ist Dir wichtiger, möglichst enge Gruppen, möglichst gleich große Gruppen, möglichst wenig Gruppen, etc.

[stillsen]

Danke fuer die Unterstuetzung!
Ich habe eine Implementation gefunden die fuer mich funktioniert.

Ich sortiere die Liste nach y. Iteriere ueber die Liste und nehme jeweils den ersten Gruppenwert als Vergleichswert. Ist die Differenz von y zum Vergleichswert innerhalb einer Toleranz fuege ich diesen Vergleichswert der Subliste als neues Sortierkriterium hinzu, ansonsten update ich den Vergleichswert.
Dann kann ich ueber den hinzugefuegten Vergleichswert sortieren (und somit nach Aehnlichkeit).

Code: Alles auswählen

def sort_circles(circles, limit):
    circles = sorted(circles, key=lambda x: x[1])
    old_y = circles[0][1]
    for (i,(x,y,r)) in enumerate(circles):
        if abs(old_y - y) > limit:
            old_y = circles[i][1]
        circles[i] = np.append(circles[i], old_y)

    circles = sorted(circles, key=lambda x: (x[3], x[0]))
    circles = [(x,y,r) for (x,y,r,z) in circles]
    return circles

[Sirius3]

numpy.append ist im Normalfall nicht sinnvoll, vor allem weil Du laut Beispiel ja normale Listen hast. Das hinzufügen eines Elements um es später wieder zu entfernen ist auch etwas seltsam.
Da Du aufsteigend sortierst, ist y - old_y immer positiv, das `abs` also überflüssig.
Statt eine Liste Elementweise zu ändern, erzeugt man am einfachsten eine neue.

Code: Alles auswählen

def sort_circles(circles, limit):
    last = float('-inf')
    groups = []
    for x in sorted(circles, key=lambda x: x[1]):
        if x[1] - last > limit:
            last = x[1]
        groups.append([last, x])
    groups.sort()
    return [x for _, x in groups]