比较两个Python列表的顺序

Question

我需要比较两个Python列表list1和list2的顺序，以检测list2是否乱序。

• list1是静态的，包含字符串a,b,c,d,e,f,g,h,i,j。这是“正确”的顺序。
• list2包含相同的字符串，但顺序和字符串数量可能会变化。(例如a,b,f,d,e,g,c,h,i,j或a,b,c,d,e)

我正在寻找一种有效的方法，通过将list2与list1进行比较来检测list2是否乱序。

例如，如果list2是a,c,d,e,g,i，则应返回true(因为字符串按顺序排列)。

而如果list2是a,d,b,c,e，则应返回false(因为字符串d不按顺序出现)。

- chasm

---

由于list1始终按字母顺序排列，我想知道您是否需要全部检查list2。如果您只是检查list2本身是否按字母顺序排列，那么这样做是否可行？ - Darren Haynes

Answer 1

首先，让我们定义list1：

>>> list1='a,b,c,d,e,f,g,h,i,j'.split(',')
>>> list1
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j']

虽然你的list1恰好按字母顺序排列，但我们不会假设它是这样的。无论如何，这段代码都可以正常工作。

现在，让我们创建一个无序的list2：

>>> list2 = 'a,b,f,d,e,g,c,h,i,j'.split(',')
>>> list2
['a', 'b', 'f', 'd', 'e', 'g', 'c', 'h', 'i', 'j']

以下是如何测试list2是否有序的方法：

>>> list2 == sorted(list2, key=lambda c: list1.index(c))
False

False 意味着乱序。

这里有一个顺序的示例：

>>> list2 = 'a,b,d,e'.split(',')
>>> list2 == sorted(list2, key=lambda c: list1.index(c))
True

True 表示按顺序排列。

忽略列表1中不在列表2中的元素

我们来看一个 list2 中有一个不在 list1 中的元素的情况：

>>> list2 = 'a,b,d,d,e,z'.split(',')

为了忽略不需要的元素，让我们创建list2b:

>>> list2b = [c for c in list2 if c in list1]

我们可以像以前一样进行测试：

>>> list2b == sorted(list2b, key=lambda c: list1.index(c))
True

不使用sorted的替代方法

>>> list2b = ['a', 'b', 'd', 'd', 'e']
>>> indices = [list1.index(c) for c in list2b]
>>> all(c <= indices[i+1] for i, c in enumerate(indices[:-1]))
True

- John1024

---

这个完美地运作了！谢谢。还有一个问题：如果list2包含list1中没有的字符串，我该怎么忽略它？ - chasm

@chasm 很高兴它起作用了。只需要再加一行代码来处理不需要的字符串。请查看更新后的答案。 - John1024

所有这些index调用可能会变得非常昂贵（二次时间！），而排序是一种低效的方法来判断输入是否已经排序。 - user2357112

Answer 2

既然list1看起来已经按字母顺序排列，为什么需要将其与其他列表进行比较呢？难道不能尝试以下方法吗？

def is_sorted(alist):
    return alist == sorted(alist)

print is_sorted(['a','c','d','e','g','i'])
# True

print is_sorted(['a','d','b','c','e'])
# False

- Julien Spronck

---

这种方法是可行的，但 list2 是动态且经常变化的。 - chasm

假设list1始终与您的问题中所述相同，那么我认为这是最简单的答案。您真正需要做的就是检查list2是否按字母顺序排列，而此函数将始终检查您传递给它的任何字母字符列表。 - Darren Haynes

在一般情况下，我们不能假设list1中的项目按字典顺序排列。如果可以的话，就不会有这个问题了。如果list2非常大，那么与基于sorted()的解决方案相比，普通的issorted可能会更快地线性运行并提前终止：issorted = lambda L: all(x < y for x,y in pairwise(L))。 - jfs

Answer 3

这是一个在预期的线性时间内运行的解决方案。如果 list1 一直是10个元素，而 list2 不会更长，那么这并不太重要，但是对于更长的列表，基于 index 的解决方案会遇到极端的减速问题。

首先，我们预处理 list1，以便快速找到任何元素的索引。（如果我们有多个 list2，则可以执行此操作一次，然后使用预处理的输出快速确定是否排序了多个 list2）。

list1_indices = {item: i for i, item in enumerate(list1)}

然后，我们检查list2的每个元素是否在list1中具有比list2的下一个元素更低的索引：

is_sorted = all(list1_indices[x] < list1_indices[y] for x, y in zip(list2, list2[1:]))

我们可以通过使用itertools.izip和itertools.islice来避免整个zip列表的实例化，让我们在检测到list2早期无序时节省大量工作:

# On Python 3, we can just use zip. islice is still needed, though.
from itertools import izip, islice
is_sorted = all(list1_indices[x] < list1_indices[y]
                for x, y in izip(list2, islice(list2, 1, None)))

- user2357112

---

你尝试过测量list2需要多大才能使itertools解决方案更快吗？对于is_sorted = lambda L: L == sorted(L, key=rank.__getitem__)，其中rank = list1_indices - 对于小列表可能是足够的。 - jfs

Answer 4

is_sorted = not any(list1.index(list2[i]) > list1.index(list2[i+1]) for i in range(len(list2)-1))

any函数会在迭代器中的任一项为真时返回True。我将其与生成器表达式结合起来，遍历list2的所有值，并确保它们按照list1的顺序排列。

- Natecat

Answer 5

if list2 == sorted(list2,key=lambda element:list1.index(element)):
    print('sorted')

- Hargen.Hans

---

你的第一次修订有缺陷。 - Natecat

Answer 6

假设您正在编写的列表1是字符串a、b、c、d、e、f、g、h、i，这意味着a可能是'zebra'，而字符串b实际上可能是'elephant'，因此顺序可能不是按字母顺序排列的。此外，如果一个项目在列表2中但不在列表1中，则此方法将返回false。

good_list2 = ['a','c','d','e','g','i']

bad_list2 = ['a','d','b','c','e']

def verify(somelist):
    list1 = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j']
    while len(list1) > 0:
        try:
            list1 = list1[:list1.index(somelist.pop())]
        except ValueError:
            return False
    return True

- Projski