4

这是一个问题，是什么是识别列表中连续重复项的最 Pythonic 方式的扩展？.

假设您有一个元组列表：

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

这可以在发电机内完成吗？

更新

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

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

为了明确术语，我采用了“运行”来描述TimSortPython 的排序函数所基于的内容——赋予它（排序函数）它的安全性。

因此，如果您对集合进行排序，如果集合是多面的，则仅对指定的维度进行排序，如果指定维度的两个元素相同，则它们的排序将不会改变。

因此以下功能：

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.) 使用拼接运算符，获取、反转并将每个子列表附加到空列表

4

2 回答 2

4

我认为这会奏效。

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")])))
于 2017-01-27T16:13:49.937 回答
2

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

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

我们可以像这样多次排序，因为python的排序算法保证是稳定的。

然而，在现实生活中，通常可以简单地构建一个更聪明的键函数，允许一次进行排序。这通常涉及“否定”其中一个值并依赖于元组按字典顺序排列自己的事实：

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进来的地方。

如果我们想变得更聪明，从算法的角度来看我们可能会做得更好（假设垃圾箱的“密钥”是可散列的）。诀窍是在字典中对对象进行分类，然后对这些分类进行排序。这意味着我们可能会排序一个比原始列表短得多的列表：

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 中，那么这个算法可能不会打败它（不过，我会把它作为练习留给你尝试......）。但是，如果数据分散良好（导致TimSort行为更像MergeSort），那么首先进行分箱可能会取得轻微的胜利。

于 2017-01-27T16:17:38.733 回答