Produce all possible equivalent sorts for a given key function

Question

Say I have points:

points = [(1., 1.), (3., 0.), (-1., -1.), (9., 2.), (-4., 2.) ]

If I sort them by y axis:

 points = sorted(points , key=lambda k: [k[1], k[0]])

I get

 points = [(-1., -1.),  (3., 0.), (1.,1.) , (-4.,2.), (9., 2.)]

However I want to sort it completely independent from the x axis. Further, I want the output to be the 2 lists which show both possible sorts (i.e. all permutations of the x-values where the y-values are equal):

[(-1., -1.),  (3., 0.), (1.,1.) , (-4.,2.),(9., 2.)]
[(-1., -1.),  (3., 0.), (1.,1.) , (9.,2.), (-4.,2.)]

Is there a way I can do this?

Answer 1

Problem statement:

Create multiple lists of all possible permutations of sorts given an equivalence relation (such as comparing y-coodinates and ignoring the x-coordinates):

Solution:

Here is some working code to solve the problem:

from operator import itemgetter
from itertools import groupby, product, permutations, chain

points = [(1., 1.),  (3., 0.),(-1., -1.) , (9., 2.), (-4., 2.) ]
points.sort(key=itemgetter(1))
groups = [list(permutations(g)) for k, g in groupby(points, itemgetter(1))]
for t in product(*groups):
    print(list(chain.from_iterable(t)))

Final Result:

[(-1.0, -1.0), (3.0, 0.0), (1.0, 1.0), (9.0, 2.0), (-4.0, 2.0)]
[(-1.0, -1.0), (3.0, 0.0), (1.0, 1.0), (-4.0, 2.0), (9.0, 2.0)]

Explanation:

• The initial sort orders the points by the y-axis only. This uses itemgetter() to extract field 1.

• The groupby() step makes groups of points that have the same y-coordinate.

• The permutations() step generates all possible orderings of each group.

• The product() step generates the cartesian product of each of the permutation groups (so that each output has one element from each of the permutation groups).

• The chain.from_iterable() step links consecutive tuples in the product into a single iterable which can be fed into list() to make the desired result.

Step-by-step:

1) Sort the points by the y-coordinate, ignoring the x-coordinate:

>>> points = [(1., 1.),  (3., 0.),(-1., -1.) , (9., 2.), (-4., 2.)]
>>> points.sort(key=itemgetter(1))
>>> points
[(-1.0, -1.0), (3.0, 0.0), (1.0, 1.0), (9.0, 2.0), (-4.0, 2.0)]
>>>       ^-----------^-----------^-----------^-------------^ ascending y-values

2) Create groups of points that have the same y-coordinate:

>>> pprint([list(g) for k, g in groupby(points, itemgetter(1))], width=40)
[[(-1.0, -1.0)],                                            # y = -1.0  
 [(3.0, 0.0)],                                              # y =  0.0
 [(1.0, 1.0)],                                              # y =  1.0 
 [(9.0, 2.0), (-4.0, 2.0)]]                                 # y =  2.0 

3) Generate all permutations of points that have the same y-coordinate:

>>> groups = [list(permutations(g)) for k, g in groupby(points, itemgetter(1))]
>>> pprint(groups)
[[((-1.0, -1.0),)],                                         # y = -1.0
 [((3.0, 0.0),)],                                           # y =  0.0 
 [((1.0, 1.0),)],                                           # y =  1.0 
 [((9.0, 2.0), (-4.0, 2.0)), ((-4.0, 2.0), (9.0, 2.0))]]    # y =  2.0

4) Create all possible sequences with one element from each permutation group:

>>> for t in product(*groups):
        print(t)

(((-1.0, -1.0),), ((3.0, 0.0),), ((1.0, 1.0),), ((9.0, 2.0), (-4.0, 2.0)))
(((-1.0, -1.0),), ((3.0, 0.0),), ((1.0, 1.0),), ((-4.0, 2.0), (9.0, 2.0)))

5) Combine each subsequence into a single list:

>>> for t in product(*groups):
        list(chain.from_iterable(t))

[(-1.0, -1.0), (3.0, 0.0), (1.0, 1.0), (9.0, 2.0), (-4.0, 2.0)]
[(-1.0, -1.0), (3.0, 0.0), (1.0, 1.0), (-4.0, 2.0), (9.0, 2.0)]