Python 3: Обратные последовательные прогоны в отсортированном списке?

Question

Этот вопрос есть расширение What's the most Pythonic way to identify consecutive duplicates in a list?.

Предположим, у вас есть список кортежей:

my_list = [(1,4), (2,3), (3,2), (4,4), (5,2)] 

и вы сортировать его последнее значение каждого кортежа:

my_list = sorted(my_list, key=lambda tuple: tuple[1]) 
# [(3,2), (5,2), (2,3), (1,4), (4,4)] 

тогда мы имеем два последовательных прогонов (глядя на последнее значение в каждой кортеж), а именно [(3,2), (5,2)] и [(1,4), (4,4)].

Что такое pythonic способ отменить каждый прогон (а не кортежи внутри), например.

reverse_runs(my_list) 
# [(5,2), (3,2), (2,3), (4,4), (1,4)] 

Это можно сделать в генераторе?

UPDATE

Он пришел к мое внимание, что, возможно, пример списка не было ясно. Поэтому вместо того, чтобы рассмотреть следующие вопросы:

my_list = [(1,"A"), (2,"B"), (5,"C"), (4,"C"), (3,"C"), (6,"A"),(7,"A"), (8,"D")] 

Где идеальный выход из reverse_runs будет

[(7,"A"), (6,"A"), (1,"A"), (2,"B"), (3,"C"), (4,"C"), (5,"C"), (8,"D")] 

Чтобы быть ясно, по терминологии, я приняв использование «запуска», используемый в описании TimSort что и в Python функция сортировки основана на - обеспечении ее (функции сортировки) ее безопасности.

Таким образом, если вы сортировать по коллекции, если коллекция будет многогранным, то только указанный размер отсортирован по и, если два элемента в же для указанного измерения, их порядок будет не быть изменен.

Таким образом, следующая функция:

sorted(my_list,key=lambda t: t[1]) 

выходы:

[(1, 'A'), (6, 'A'), (7, 'A'), (2, 'B'), (5, 'C'), (4, 'C'), (3, 'C'), (8, 'D')] 

и работать на "C" (т.е. (5, 'C'), (4, 'C'), (3, 'C')) не нарушается.

Таким образом, в заключение желаемый результат от еще не определена функция reverse_runs:

1.) сортирует кортежи от последнего элемента

2.) поддержание порядка первого элемента, меняет прогонов на последнем элементе

В идеале я хотел бы это сделать в генераторных функциях, но это не так (для меня на данный момент) представляется возможным.

Таким образом, можно было бы принять следующую стратегию:

1.) Сортировка кортежей по последнему элементу через sorted(my_list, key=lambda tuple: tuple[1])

2.) Определите индексы для последнего элемента в каждом кортеже, когда следующий кортеж (i + 1) отличается от последнего элемента в (i). т.е. определить пробеги

3.) Сделайте пустой список

4.) Использование оператора сращивания, получаем, реверс, и Дописывать каждый подсписок в пустой список

Answer 1

Наиболее общий случай требует 2 сорта. Первый сорт - это сортировка reversed по второму критерию. Второго родом является прямой сортировкой по первому критерию:

pass1 = sorted(my_list, key=itemgetter(0), reverse=True) 
result = sorted(pass1, key=itemgetter(1)) 

Мы можем сортировать в нескольких проходах, как это потому, что алгоритм сортировки питона гарантированно будет stable.

Однако в реальной жизни часто можно просто построить более умную ключевую функцию, которая позволяет сортировать в один проход. Это обычно включает в себя «отрицающая» один из ценностей, опираясь на то, что кортежи заказать себе lexicographically:

result = sorted(my_list, key=lambda t: (t[1], -t[0])) 

---

В ответ на ваше обновление, это выглядит как следующий может быть подходящим решением:

from operator import itemgetter 
from itertools import chain, groupby 
my_list = [(1,"A"), (2,"B"), (5,"C"), (4,"C"), (3,"C"), (6,"A"),(7,"A"), (8,"D")] 

pass1 = sorted(my_list, key=itemgetter(1)) 
result = list(chain.from_iterable(reversed(list(g)) for k, g in groupby(pass1, key=itemgetter(1)))) 
print(result) 

Мы можем разобрать выражение:

chain.from_iterable(reversed(list(g)) for k, g in groupby(pass1, key=itemgetter(1))) 

, чтобы попытаться выяснить, что он делает ...

Во-первых, давайте посмотрим на groupby(pass1, key=itemgetter(1)). groupby даст 2-х кортежей. Первый элемент (k) в кортеже - это «ключ» - например, все, что было возвращено с itemgetter(1). Ключ не имеет особого значения после группировки, поэтому мы его не используем. Второй элемент (g - для «группы») является итерируемым, который дает последовательные значения, имеющие один и тот же «ключ». Это именно те предметы, которые вы запросили, однако они находятся в том порядке, в котором они были после сортировки. Вы запросили их в обратном порядке.Чтобы отменить произвольный итерируемый, мы можем построить список из него, а затем отменить список. например reversed(list(g)). Наконец, нам нужно снова вставить эти куски, где находится chain.from_iterable.

Если мы хотим стать более умными, мы могли бы сделать лучше с алгоритмической точки зрения (если предположить, что «ключ» для ящиков является hashible). Хитрость заключается в том, чтобы выровнять объекты в словаре, а затем сортировать бункеры. Это означает, что мы потенциально сортировки гораздо более короткий список, чем оригинал:

from collections import defaultdict, deque 
from itertools import chain 

my_list = [(1,"A"), (2,"B"), (5,"C"), (4,"C"), (3,"C"), (6,"A"),(7,"A"), (8,"D")] 

bins = defaultdict(deque) 
for t in my_list: 
    bins[t[1]].appendleft(t) 

print(list(chain.from_iterable(bins[key] for key in sorted(bins)))) 

Обратите внимание, что ли это делает лучше, чем первый подход очень зависит от исходных данных. Так как TimSort - такой красивый алгоритм, если данные начинаются уже сгруппированными в бункеры, то этот алгоритм, скорее всего, не побьет его (хотя я оставлю его как упражнение для вас попробовать ...). Однако, если данные хорошо разбросаны (вызывают TimSort, чтобы вести себя как MergeSort), то сначала биннинг может сделать небольшую победу.

Answer 2

Я думаю, что это будет работать.

my_list = [(1,4), (2,3), (3,2), (4,4), (5,2)] 
my_list = sorted(my_list, key=lambda tuple: (tuple[1], -tuple[0])) 

print(my_list) 

Выход

[(5, 2), (3, 2), (2, 3), (4, 4), (1, 4)] 

---

Misunderstood вопрос. Менее красиво, но это должно работать на то, что вы действительно хотите:

from itertools import groupby 
from operator import itemgetter 


def reverse_runs(l): 
    sorted_list = sorted(l, key=itemgetter(1)) 
    reversed_groups = (reversed(list(g)) for _, g in groupby(sorted_list, key=itemgetter(1))) 
    reversed_runs = [e for sublist in reversed_groups for e in sublist] 

    return reversed_runs 


if __name__ == '__main__': 
    print(reverse_runs([(1, 4), (2, 3), (3, 2), (4, 4), (5, 2)])) 
    print(reverse_runs([(1, "A"), (2, "B"), (5, "C"), (4, "C"), (3, "C"), (6, "A"), (7, "A"), (8, "D")])) 

Выход

[(5, 2), (3, 2), (2, 3), (4, 4), (1, 4)] 
[(7, 'A'), (6, 'A'), (1, 'A'), (2, 'B'), (3, 'C'), (4, 'C'), (5, 'C'), (8, 'D')] 

---

Generator версии:

from itertools import groupby 
from operator import itemgetter 


def reverse_runs(l): 
    sorted_list = sorted(l, key=itemgetter(1)) 
    reversed_groups = (reversed(list(g)) for _, g in groupby(sorted_list, key=itemgetter(1))) 

    for group in reversed_groups: 
     yield from group 


if __name__ == '__main__': 
    print(list(reverse_runs([(1, 4), (2, 3), (3, 2), (4, 4), (5, 2)]))) 
    print(list(reverse_runs([(1, "A"), (2, "B"), (5, "C"), (4, "C"), (3, "C"), (6, "A"), (7, "A"), (8, "D")])))