确定一个列表中的所有元素是否按照相同的顺序出现在另一个列表中。

Question

如何创建一个名为 sublist() 的函数，该函数接受两个列表 list1 和 list2 作为参数，并返回True 如果 list1 是 list2 的子列表，否则返回False。如果在 list1 中的数字按照它们在 list1 中出现的顺序出现在 list2 中，但不一定是连续的，则认为 list1 是 list2 的子列表。例如:

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

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

- user3638865

---

在某些复杂度要求内？ - Ryan Haining

列表中的项目可以重复吗？ - grdvnl

我最初认为你的问题与这个非常相似：https://dev59.com/Bm865IYBdhLWcg3wYNdS，但经过检查，它并不是。请考虑修改你的问题，避免它被关闭为重复，并使其他试图做同样事情的用户更容易找到答案。 - jpmc26

@user3638865，我注意到你已经发布了6个问题，但没有一个被标记为“已回答”。通过点击你认为合适的答案旁边的“勾选标记”，来选择一个答案。 - bcorso

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()。

- hetman

---

至少在Python 3中，这需要是seq.__next __() - 对列表进行迭代返回一个没有next方法的对象，只有__next__。 - Peter DeGlopper

查看我的回答，其中包含了一些不太严谨的性能测试，表明这种方法比我的回答或递归版本更快。我没有测试 @sshashank124 的方法，但正如你指出的那样，复制列表会有成本。 - Peter DeGlopper

тйЊуёХ - Сй┐ућеnext(seq)УђїСИЇТў»seq.__next__()сђѓТў»уџё№╝їУ┐ЎТў»ТГБуА«уџёТќ╣Т│Ћсђѓ - Peter DeGlopper

如果有人需要微调这个，我怀疑 itertools.dropwhile(x.__ne__, seq) 可能比显式循环更快（因为它在 C 中迭代），或者带有 break 的 for 循环（因为它使用更少的字节码进行迭代）可能比围绕 next 的 while 循环更快，特别是在 CPython 2.x 中。我怀疑对于大多数真实代码来说，这并不重要，但如果确实如此，有两件事情需要测试。 :) - abarnert

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

编辑：速度升级

- huu

---

非常粗糙，但我相信这是所有情况下都正确的第一个。但是执行时间太长了！:O。仍然+1，它比我的全面性更好。 - Adam Smith

我认为，我的解决方案最多只会读取每个数组一次。如果我错了，请纠正我，但这就是最快的方法，对吧？ - huu

我想对比一下我的迭代实现和这个，但这看起来既正确又优雅。 - Peter DeGlopper

不要过度劳累，否则你会达到递归深度限制 :P - huu

是的，这是一个很酷的演示，但不太适用于实际应用。这里的主要问题首先是它创建子列表副本，这将使得随着输入规模的增大，速度变得非常慢和占用内存非常多。其次是你指出的递归深度限制 ;) - hetman

Answer 3

这里是简化版：

def sublist(a,b):
    try:
        return a[0] in b and sublist(a[1:],b[1+b.index(a[0]):])
    except IndexError:
        return True

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

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

- sshashank124

---

如果允许重复项，则无法正常工作。例如在 sublist([1, 2, 2], [1, 2, 3]) 中返回 "True"。 - Sergii Dymchenko

递归调用中应该是 b[1+b.index(a[0]):]，对吧？这样就可以正确处理重复项了。 - Alp

@Alp，非常感谢。我已经更新了我的答案。 - sshashank124

Answer 4

这是一个迭代解决方案，其渐进复杂度应该是最优的：

def sublist(x, y):
    if x and not y:
        return False
    i, lim = 0, len(y)
    for e in x:
        while e != y[i]:
            i += 1
            if i == lim:
                return False
        i += 1
    return True

@sshashank124的解决方案具有相同的复杂度，但动态性将有所不同：他的版本多次遍历第二个参数，但由于它将更多的工作推入C层，因此在较小的输入上速度可能会更快。

编辑：@hetman的解决方案基本上具有相同的逻辑，但更符合Pythonic风格，尽管与我的预期相反，它似乎略慢一些。（我关于@sshashan124解决方案的性能也是错误的；递归调用的开销似乎超过了在C中做更多工作的好处。）

- Alp

---

你确定@sshashank124的解决方案具有相同的复杂度吗？它正在创建子列表的副本，这意味着空间复杂度肯定会更高。 - hetman

我只考虑了时间复杂度。 - Alp

Answer 5

恭喜你提出了一个看似简单实则很难的问题。我认为这个解决方案可以工作，但如果有重复元素，我不会感到惊讶如果我错过了某些角落情况。受Hgu Nguyen递归解决方案的启发，修订后的版本如下：

def sublist(a, b):
    index_a = 0
    index_b = 0
    len_a = len(a)
    len_b = len(b)
    while index_a < len_a and index_b < len_b:
        if a[index_a] == b[index_b]:
            index_a += 1
            index_b += 1
        else:
            index_b += 1
    return index_a == len_a

一些简单的分析：

对于需要遍历大部分或全部 b 的列表，我的算法会受到影响：

a = [1, 3, 999999]
b = list(range(1000000))

在我的电脑上，Huu Nguyen或Hetman算法运行100次迭代检查需要约10秒。而我的算法需要20秒。

鉴于早期的成功，Huu的算法落后很多：

a = [1, 3, 5]

Hetman's算法或者我的算法可以在不到一秒的时间内完成10万次检测-Hetman's算法仅需0.13秒，在我的电脑上，而我的算法则需要0.19秒。Huu的算法需要16秒才能完成1千次检测。我对这种差异感到惊讶-递归可能会很慢，如果没有编译器优化的话。但是4个数量级的差距比我预想的要糟糕得多。

给定一个错误列表a，性能返回到了当我需要遍历整个第二个列表时看到的情况-可以理解，因为无法知道最终是否会有一个与其余难以匹配的列表相匹配的序列。

a = [3, 1, 5]

关于100个测试的Huu Nguyen或Hetman算法，需要约10秒钟，而我的算法需要20秒钟。

更长的有序列表保持了我早期成功看到的模式。例如：

a = range(0, 1000, 20)

使用Hetman算法，完成100k次测试所需时间为10.99秒，而我的算法需要24.08秒。Huu的算法需要28.88秒才能完成100次测试。

尽管这并不是您可以运行的所有测试范围，但在所有情况下，Hetman的算法表现最佳。

- Peter DeGlopper

---

优秀的分析。是的，我有一种感觉我的代码还不够优化。看到这里对不同情况进行了全面比较真是太好了。 - huu

@HuuNguyen - 我只能想到在早期的成功案例中，复制大部分 b 的时间会使递归版本受到影响。在我的简单测试用例中，它只需要执行三次（匹配 1、3 和 5 后），但似乎会累加。您可以通过将起始索引 k 传递到 b 中，并将未复制的列表引用传递到递归调用中来进行一些优化，然后执行 for k in range(starting_index, len(b)): - 但我认为 @Hetman 的方法仍然更好。长列表 b 强调了复制成本，但总体而言，我认为它是 O(a*b)，因为您要将 b 的部分复制 len(a) 次。 - Peter DeGlopper

Answer 6

这里有另一种解决方案，可能比Hetman's更易于新手理解。（请注意，它与this duplicate question中的实现非常接近，但避免了每次从b的开头重新开始搜索的问题。）

def sublist(a, b):
    i = -1
    try:
        for e in a:
            i = b.index(e, i+1)
    except ValueError:
        return False
    else:
        return True

当然，这需要b是一个列表，而Hetman的答案允许任何可迭代对象。我认为（对于那些足够了解Python的人来说），它比Hetman的答案更复杂。

从算法上讲，它与Hetman的答案做的是相同的事情，因此时间复杂度为O(N)，空间复杂度为O(1)。但在实践中，它可能会更快，至少在CPython中，因为我们将内部循环从Python的while移到了C的快速获取索引循环（在list.index内部）。另一方面，它可能会更慢，因为我们正在复制该 i 值，而不是将所有状态嵌入到（由C实现的）迭代器中。如果有影响，请使用您的真实数据测试它们。 :)

- abarnert

Answer 7

如何这样：让我们从另一个角度来看待这个问题：

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] 的子集），但很难确定您想要如何实现...

- Adam Smith

Answer 8

如果需要一个快速而简单的解决方案，虽然运行速度较慢，但对于您展示的数组大小完全足够：

def sublist(a,b):
    last = 0
    for el_a in a:
        if el_a in b[last:]:
             last = b[last:].index(el_a)
        else:
             return False
    return True

**已更新以适用于非连续元素

- John Haberstroh

---

差一点，但还不够。他的第一个例子在这里测试为假。 - Adam Smith

第一次我也没有这样做，而是使用了 set.issubset 的解决方案。 - Adam Smith

Answer 9

这里有一个更好的解决方案，使用正则表达式：

import re


def exiSt(short,long):
    r = ''.join(["(.*"+str[x]+")" for x in short])
    return re.match(r,','.join([str(x) for x in long])) == None

long = [1, 2, 3, 4, 5]
short1 = [1,2,5]
short2 = [1,5,3]

exiSt(short1,long)
>> True

exiSt(short2,long)
>> False

- farhawa

Answer 10

def sublist(a, b):
    "if set_a is not subset of set_b then obvious answer is False"
    if not set(a).issubset(set(b)):
        return False
    n = 0
    for i in a:
        if i in b[n:]:
            "+1 is needed to skip consecutive duplicates, i.e. sublist([2,1,1],[2,1]) = False"
            "if +1 is absent then sublist([2,1,1],[2,1]) = True"
            "choose to use or not to use +1 according to your needs"
            n += b[n:].index(i) + 1
        else:
            return False
    return True

- Trigremm