Произведите все возможные эквивалентные сортировки для данной ключевой функции

Question

Скажи, что у меня есть очки:

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

Если я сортирую их по оси Y:

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

я получил

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

Однако я хочу отсортировать его полностью независимо от оси х. Кроме того, я хочу, чтобы выходные данные были 2 списками, которые показывают оба возможных вида (т. Е. Все перестановки значений x, где значения y равны):

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

Есть ли способ, которым я могу сделать это?

Answer 1

Постановка задачи:

Создайте несколько списков всех возможных вариантов перестановок с учетом отношения эквивалентности (например, сравнивая y-coodinates и игнорируя x-координаты):

Решение:

Вот некоторый рабочий код для решения проблемы:

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

Конечный результат:

[(-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)]

Объяснение:

• Первоначальная сортировка упорядочивает точки только по оси Y. Это использует itemgetter() для извлечения поля 1.

• Шаг groupby() создает группы точек с одинаковыми координатами y.

• Шаг permutations() генерирует все возможные упорядочения каждой группы.

• Шаг product() генерирует декартово произведение каждой из групп перестановок (так, чтобы у каждого выхода был один элемент из каждой из групп перестановок).

• Шаг chain.from_iterable () связывает последовательные кортежи в продукте в одну итерацию, которая может быть передана в list () для получения желаемого результата.

Шаг за шагом:

1) Сортировка точек по y-координате, игнорируя x-координату:

>>> 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) Создайте группы точек с одинаковыми координатами y:

>>> 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) Генерация всех перестановок точек, имеющих одинаковую y-координату:

>>> 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) Создайте все возможные последовательности с одним элементом из каждой группы перестановок:

>>> 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) Объединить каждую подпоследовательность в один список:

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

Answer 2

Сортировать только по значениям x:

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

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