Python：在一个列表中按顺序查找另一个列表

Question

如果我有这个：

a='abcdefghij'
b='de'

那么这个可以在a中找到b：

b in a => True

有没有类似的方法可以用在列表上？像这样：

a=list('abcdefghij')
b=list('de')

b in a => False 

结果是'False'是可以理解的——因为它确实在寻找元素'de'，而不是（我希望它能做的）'d'后面跟着'e'

我知道这个是可以工作的：

a=['a', 'b', 'c', ['d', 'e'], 'f', 'g', 'h']
b=list('de')
b in a => True

我可以处理数据来得到我想要的结果——但是有没有更简洁的Python方式来做到这一点？

为了更清楚：我需要保持顺序（b=['e','d']，应该返回False）。

如果有帮助的话，我有一个列表的列表：这些列表代表从节点1到节点x在有向图中所有可能的路径（一个访问过的节点列表）：我想要'提取'出任何更长路径中的共同路径。（所以是在寻找所有不可简化的'原子'路径，这些路径构成了所有更长的路径）。

相关链接

• 在Python中判断一个序列是否在另一个序列中的最佳方法

Answer 1

我觉得这个方法会更快一些，因为它使用了C语言实现的 list.index 来查找第一个元素，然后再继续处理。

def find_sublist(sub, bigger):
    if not bigger:
        return -1
    if not sub:
        return 0
    first, rest = sub[0], sub[1:]
    pos = 0
    try:
        while True:
            pos = bigger.index(first, pos) + 1
            if not rest or bigger[pos:pos+len(rest)] == rest:
                return pos
    except ValueError:
        return -1

data = list('abcdfghdesdkflksdkeeddefaksda')
print find_sublist(list('def'), data)

需要注意的是，这个方法返回的是子列表在列表中的位置，而不仅仅是 True 或 False。如果你只想要一个 bool 值，可以用这个方法：

def is_sublist(sub, bigger): 
    return find_sublist(sub, bigger) >= 0

Answer 2

我觉得可能有更符合Python风格的方法来实现这个功能，但至少这个方法能完成任务：

l=list('abcdefgh')
pat=list('de')

print pat in l # Returns False
print any(l[i:i+len(pat)]==pat for i in xrange(len(l)-len(pat)+1))

Answer 3

我不知道这样做是否很符合Python的风格，但我会这样做：

def is_sublist(a, b):
    if not a: return True
    if not b: return False
    return b[:len(a)] == a or is_sublist(a, b[1:])

在这个讨论中提供了更简短的解决方案，但它和使用set的方案有同样的问题——没有考虑元素的顺序。

更新：
受到MAK的启发，我对我的代码进行了更简洁明了的改进。

更新：
这个方法在性能上有一些问题，因为在切片时会复制列表。而且，由于它是递归的，对于很长的列表，你可能会遇到递归限制。为了避免复制，你可以使用Numpy的切片，它创建的是视图，而不是复制。如果你遇到性能或递归限制的问题，应该使用不带递归的解决方案。