sort lists of lists with multiple criteria: similar values need to be treated equal

[stillsen]

Hi,
I want to sort a list of lists according to multiple criteria, in a way that similar values are treated as equals.
Let's get into details.
There is a list that contains up to 12 lists with values (x, y, r).

 
 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]]
 

I want to sort the list according to the first criteria y and than according to the second x.
So far so easy.

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

The Problem is, that for some 3 sublists y values are similar but not identical, though for sorting I need them to be treated as equals, such that I can sort according to the second criteria x.
1) sort ~ y
2) sort x

i need something like:

[ x, y, r]

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

My first idea was to sort the list firstly by y and than secondly sort it's sublists by x.

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

But it doesn't seem to work?!

Does anybody has an idea, how to sort such lists of lists with first criteria according to similar values of y and than secondly by x values?

Thanks a lot!

[ichabod801]

Well, you haven't defined what you mean by similar. Obviously you know how to sort using key functions. If you can define a function such that all similar values get transformed into the same value, you can just use a key function. For example, if you want to ignore the ones digit, you could just use lambda x: x[1] // 10, x[0].

But say your similarity is "within 10 of the next value". That you can't define a simple function for. You may need to augment your lists with a fourth value. That is, sort by y. Then add a fourth item to each sublist that is the same as the previous sublist's fourth value if they are within 10 of each other, otherwise it's one greater. Then sort by the fourth item and the first item (x).

[stillsen]

Hey ichabod!
Thank you very much for your input, it helped a lot!

First, i defined similarity as deviation of y towards the group mean within a certain tolerance. As i do not need so precise, I defined as deviation towards the first element of the group within a certain tolerance.
I implemented it as you suggested - I first sort it according to y, then augment the list with a 4th, group common similarity value and use this as first search criteria. This group common similarity value, I defined to be the first value of such a group and to be updated if the difference exceeds a limit.

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