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

然后我们有两个连续的运行s（查看每个元组中的最后一个值），即[(3,2), (5,2)]和[(1,4), (4,4)]。

反转每个运行（不是其中的元组）的 pythonic 方法是什么，例如

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

这可以在生成器中完成吗？

更新

我注意到示例列表可能不清楚。因此，请考虑：

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.) 维护第一个元素的顺序，在最后一个元素

上反转运行s

理想情况下，我希望在生成器函数中这样做，但（目前对我而言）似乎不可能。

因此可以采取以下策略：

1.) 通过 sorted(my_list, key=lambda tuple: tuple[1])

按最后一个元素对元组进行排序

2.) 当后续元组 (i+1) 与 (i) 中的最后一个元素不同时，识别每个元组中最后一个元素的索引。即识别运行s

3.) 创建一个空列表

4.) 使用拼接运算符，获取、反转并将每个子列表追加到空列表

Answer 1

我认为这会奏效。

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

生成器版本：

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

Answer 2

最一般的情况需要2种。第一种排序是 reversed 根据第二个条件排序。第二种排序是基于第一种标准的正向排序：

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

我们可以像这样分多次排序，因为python的排序算法保证是stable.

然而，在现实生活中，通常可以简单地构造一个更聪明的键函数，让排序在一次传递中发生。这通常涉及 "negating" 值之一，并依赖于元组自行排序的事实 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 将产生二元组。元组中的第一项 (k) 是 "key" —— 例如从 itemgetter(1) 返回的任何内容。分组发生后密钥在这里并不重要，因此我们不使用它。第二项（g -- 对于 "group"）是一个迭代器，它产生具有相同 "key" 的连续值。这正是您要求的项目，但是，它们是按排序后的顺序排列的。您以相反的顺序请求它们。为了反转任意可迭代对象，我们可以从中构造一个列表，然后反转该列表。例如reversed(list(g))。最后，我们需要将这些块再次粘贴在一起，这就是 chain.from_iterable 的用武之地。

如果我们想变得更聪明，我们可能会从算法的角度做得更好（假设 bin 的 "key" 是可哈希的）。诀窍是将对象放入字典中，然后对这些箱子进行排序。这意味着我们可能会排序一个比原始列表短得多的列表：

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 是一个非常漂亮的算法，如果数据开始时已经分组到 bins 中，那么这个算法可能不会击败它（不过，我会把它作为练习留给你尝试......）。但是，如果数据分散得很好（导致 TimSort 表现得更像 MergeSort），那么先分箱可能会略胜一筹。

Python 3：在排序列表中反向连续运行？

Python 3: Reverse consecutive runs in sorted list?

python

algorithm

list

generator

timsort

更新