从列表中查找有序子序列(不一定是连续的)

Question

我遇到了问题.我有一个列表,例如[A,B,C,D,E].列表的大小可能会有所不同.我必须检查是否[A,C,E]在主列表中出现了例如子序列.子序列的大小也可以变化.

这里的问题是这里的子序列不需要是连续的.只是发生的顺序很重要.

一些例子:

seq = [A,B,C,D,E]

subseq = [A,C,E]
>>>sub-sequence present in sequence

subseq = [B,D,E]
>>> sub-sequence present in sequence

subseq = [A,E]
>>> sub-sequence present in sequence

subseq = [C,B]
>>> sub-sequence not present in sequence

subseq = [B,A,E]
>>> sub-sequence not present in sequence

Answer 1

您可以使用iter生成迭代器,其消耗强制执行每个成员检查的顺序.

def subcheck(li, sub_li):
    it = iter(li)
    return all(el in it for el in sub_li)

演示

In[95]: subcheck([1, 6, 3, 9, 4, 2], [1, 9, 3])
Out[95]: False

In[96]: subcheck([1, 6, 3, 9, 4, 2], [1, 3, 9])
Out[96]: True

这种方法有效,因为in列表的关键字实现为序列迭代(文档):

对于容器类型,例如list,tuple,set,frozenset,dict或collections.deque,表达式x in y等效于any(x is e or x == e for e in y).