比较Python列表中元素的顺序

Question

我正在尝试写一个函数，如果 lst1 中的元素按照它们在 lst1 中出现的顺序出现在 lst2 中，就返回 True，但不要求它们是连续的。

举个例子，

test([29, 5, 100], [20, 29, 30, 50, 5, 100]) 应该返回 True。

test([25, 65, 40], [40, 25, 30, 65, 1, 100]) 应该返回 False。

这是我目前的代码：

def test(lst1, lst2):
    for i in range(len(lst1)-len(lst2)+1):
        if lst2 == lst1[i:i+len(lst2)]:
            return True 
    return False 

Answer 1

这个方法会扫描列表，采用了一种不同的方式：

def test(lst1, lst2):
    p2 = 0
    length = len(lst2)
    for e1 in lst1:
        for p in range(p2, length):
            if e1 == lst2[p]:
                p2 = p
                break
        else:
            return False    
    return True

对于lst1中的每一个元素，它会在列表2的一个子集（从p2到列表的末尾）中查找这个元素。如果找到了，就会通过更新p2来限制后续查找的范围。如果没有找到，就返回False。如果lst1中的每个元素都找到了，就返回True。

Answer 2

递归地，不要覆盖列表，不要创建新的子列表，尽早失败

def find_all(needle, haystack, npos=0, hpos=0):
  if npos >= len(needle):
    return True
  try:
    return find_all(needle, haystack, npos+1, haystack.index(needle[npos], hpos)+1) 
  except ValueError:
    return False


print find_all([1,3,5], [1,2,3,4,5,6,7]) # True
print find_all([1,5,3], [1,2,3,4,5,6,7]) # False

Answer 3

这里有一个使用 index 的迭代版本方法，这是 Triptych 提供的。我觉得这可能是最好的做法，因为 index 的速度应该比手动索引或迭代要快：

def test(lst1, lst2):
    start = 0
    try:
        for item in lst1:
            start = lst2.index(item, start) + 1
    except ValueError:
        return False
    return True

在 Python 中，这种方法的表现应该比递归版本要好。而且它在每次搜索后会正确地将起始点加一，这样在第一个列表中有重复项时，就不会出现错误的结果。

这里有两个解决方案，它们主要是对 lst2 进行迭代，而不是 lst1，但在其他方面与 jedwards 的版本类似。

第一个方法很简单，使用了索引，但只有在你实际移动到 lst1 中的不同项时才会进行索引，而不是对 lst2 中的每一项都进行索引：

def test(lst1, lst2):
    length, i, item = len(lst1), 0, lst1[0]
    for x in lst2:
        if x == item:
            i += 1
            if i == length:
                return True
            item = lst1[i]
    return False

第二个方法则是手动对 lst1 进行迭代，使用 next 而不是索引：

def test(lst1, lst2):
    it = iter(lst1)
    try:
        i = next(it)
        for x in lst2:
            if x == i:
                i = next(it)
    except StopIteration:
        return True
    return False

这两种方法可能都是小幅改进，因为它们减少了索引的次数，并且不需要为 lst1 中的每一项构建一个 range。