how to sort an array with a specific logic-CodePudding

I wish to sort the following array in such way that the 'distance' between the events are the largest.

example:

events =  [[1,2],[2,8],[3,4],[1,2]]

the end result should be:

events =  [[1,2],[1,2],[3,4],[2,8]]

why? consider [1:2] where x=1 and y=2 so x must comes first unless if y-x is larger then it should be pushed further away. in the example it has [2:8] which means the distance is 6

what have I done?

events = sorted(events, key = lambda x: x[0])

result:

[[1, 2], [1, 2], [2, 8], [3, 4]]

but I couldnt figure our how to add another logic for the distance

CodePudding user response：

Same as you did, just sort by the delta between the numbers:

events = sorted(sorted(events), key = lambda x: x[1]-x[0])

Since Python's sort is a stable algorithm, first sorting normally ensures [[1,2], [1,2], [3,4]] will stay in that order, and then you can sort by distance.

>>> events =  [[1,2],[2,8],[3,4],[1,2]]
>>> events = sorted(sorted(events), key = lambda x: x[1]-x[0])
>>> events
[[1, 2], [1, 2], [3, 4], [2, 8]]

A different (but close) solution:

events = sorted(events, key = lambda x: (x[1]-x[0], x[0]))

I don't have a preference for either one. On timing tests both are quite similar on a 400-item list, but I guess it highly depends on starting conditions such as list size and list values:

py -m timeit -s "events = [[1,2],[2,8],[3,4],[1,2]]*100" "sorted(sorted(events), key = lambda x: x[1]-x[0])"
1000 loops, best of 5: 214 usec per loop
py -m timeit -s "events = [[1,2],[2,8],[3,4],[1,2]]*100" "sorted(events, key = lambda x: (x[1]-x[0], x[0]))"
1000 loops, best of 5: 220 usec per loop

CodePudding user response：

Is this what you're looking for?

events = sorted(events, key = lambda x: x[1] - x[0])

This sorts such that those pairs with a larger difference will be at the end of the list and those with a smaller difference at the start. If negative differences can occur those will be the first.

CodePudding user response：

obtain lists for distance and first value, zip them in proper order, and sort

events =  [[1,2],[2,8],[3,4],[1,2]]
dist = [x[1] - x[0] for x in events]
first = [x[0] for x in events]
z = zip(dist, first, events)
[x[2] for x in sorted(z)]
# [[1, 2], [1, 2], [3, 4], [2, 8]]