确定列表中的所有元素是否存在,并且在另一个列表中是否存在相同的顺序

Question

如何创建一个带有sublist()两个列表的函数,list1并且list2,True如果list1是子列表,则返回if list2,False否则.list1是一个子列表,list2如果数字list1出现list2的顺序与它们出现的顺序相同list1,但不一定是连续的.例如,

>>> sublist([1, 12, 3],[25, 1, 30, 12, 3, 40])
True

>>> sublist([5, 90, 2],[90, 20, 5, 2, 17])
False

Answer 1

这是使用迭代器在线性时间(和常量空间)中执行此操作的一种方法:

def sublist(a, b):
    seq = iter(b)
    try:
        for x in a:
            while next(seq) != x: pass
        else:
            return True
    except StopIteration:
        pass
    return False

基本上它遍历子列表的每个元素,并查看它是否可以在完整列表的部分中找到它尚未查看的相同元素.如果它通过整个子列表,则意味着我们有匹配(因此for循环中的else语句).如果我们在完整列表中看不到要查看的元素,则表示我们没有匹配项.

编辑:我已更新我的解决方案,因此它适用于Python 3.对于Python 2.5及更早版本,next(seq)需要替换为seq.next().

Answer 2

非常粗略的解决方案:

def sublist(a, b):
    if not a:
        return True
    for k in range(len(b)):
        if a[0] == b[k]:
            return sublist(a[1:], b[k+1:])
    return False

print sublist([1, 12, 3], [25, 1, 30, 12, 3, 40]) # True
print sublist([12, 1, 3], [25, 1, 30, 12, 3, 40]) # False

编辑:速度升级

Answer 3

怎么样：让我们从另一方面来解决这个问题：

def sublist(a,b):
    """returns True if a is contained in b and in the same order"""
    return a == [ch for ch in b if ch in a]

在某些情况下这会失败（例如应该[1,2,3]是 的子集[1,1,8,2,3]），但很难确切地说出您希望如何实现它......