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

각 실행 (터플이 아닌)을 역전시키는 비유의 방법은 무엇입니까?

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

발전기 내에서 가능합니까?

UPDATE는

그것은 아마도 예를 들어 목록이 명확하지 않았다 나의주의에왔다. 그래서 그 대신 고려 : TimSort을 기술에 사용되는

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

이 용어에 명확하게하는 것입니다 경우, 내가 뭘 파이썬이다 "실행"의 사용을 채택하고 sort 함수는 그 안전성 (sort 함수)을 기반으로합니다. 두 요소가 지정된 차원의 같은을 경우

따라서 당신이 종류의 콜렉션에, 컬렉션,다면 다음에만 지정된 차원이 및에 정렬 할 필요가있는 경우, 그 순서는 을 것이다 아니 변경할 수 있습니다.

따라서 다음의 기능 :

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)가 제 1 요소의 순서를 유지하는 자신의 마지막 요소

2)에 의해 튜플 정렬, 실행 반전 마지막 요소에

이상적으로는 발전기 기능에서이 기능을 사용하고 싶지만, 그 순간에는 가능하지 않습니다.

1 :

따라서 하나는 다음과 같은 전략을 채택 할 수있다.) 튜플을 마지막 요소로 정렬 sorted(my_list, key=lambda tuple: tuple[1])

2. 후속 튜플 (i + 1)이 (i)의 마지막 요소와 다른 경우 각 튜플의 마지막 요소에 대한 인덱스를 식별합니다. 즉, 내가이 일을 생각 빈리스트

Answer 1

합니다. 첫 번째 정렬은 두 번째 조건에서 reversed 정렬입니다. 파이썬의 정렬 알고리즘은 stable이 보장되기 때문에

가

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

우리는 다음과 같은 여러 패스에 정렬 할 수 있습니다 : 두 번째 종류는 앞으로 첫 번째 기준에 일종이다.

그러나 실제로는 한 번에 정렬을 수행 할 수있는 더 영리한 키 기능을 간단히 구성 할 수 있습니다. 당신의 갱신에 대응

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

---

, 그것은 같은을 보이는 적절한 해결책이 될 수있는 다음과 같은 : 이것은 일반적으로 튜플 자신에게 lexicographically를 주문하는 것이 "무효화"값 중 하나와 사실에 의존 포함한다 :

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

0,123,516 :

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) 

우리는 표현을 분해 할 수

무엇을하고 있는지 알아 내려고 ...

먼저 groupby(pass1, key=itemgetter(1))을 살펴 보겠습니다. groupby은 2- 튜플을 산출합니다. 터플의 첫 번째 항목 (k)은 "키"입니다 (예 : itemgetter(1)에서 반환 된 항목 그룹화가 이루어진 후에 중요한 것은 여기서 중요하지 않으므로 사용하지 않습니다. 두 번째 항목 (g - "그룹"의 경우)은 동일한 "키"를 갖는 연속적인 값을 산출하는 반복 가능 항목입니다. 이것은 정확히 당신이 요청한 항목이지만, 그들은 정렬 한 순서대로되어 있습니다. 요청한 순서가 역순입니다.임의의 iterable을 뒤집으려면 목록에서 목록을 구성한 다음 목록을 역순으로 만들면됩니다. 예 : reversed(list(g)). 마지막으로, 우리는 다시 그 덩어리를 다시 붙여 넣어야합니다. 이 들어옵니다.

더 영리 해지기를 원하면 알고리즘의 관점에서 더 잘 수행 할 수 있습니다 (휴지통의 "키"가 해시 가능하다고 가정).). 트릭은 사전에있는 객체를 비우고 빈을 정렬하는 것입니다. 이 첫 번째 방법보다 더 나은 수행 여부를하면 초기 데이터에 매우 의존한다는

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이 아름다운 알고리즘이므로 데이터가 이미 bin으로 그룹화 된 경우이 알고리즘은이 알고리즘을 능가하지 못할 것입니다.하지만 시도해 볼 운동으로 남겨 두겠습니다. 그러나 데이터가 잘 분산되어 (이 MergeSort처럼 동작하는 경우), 먼저 비닝 (binning)이 약간의 승리를 이끌 것입니다.

Answer 2

에 APPEND 각 하위 목록을 스플 라이스 연산자를 사용하여 빈리스트

4) 확인을 실행

3.

)을 식별 구 역합니다.

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

---

오해 질문입니다. 적은 꽤 그러나 이것은 당신이 정말로 원하는 것을 위해 작동합니다 :

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

---

발전기 버전 : 가장 일반적인 경우는 2 개 종류가 필요

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