确定列表中的所有元素是否都存在并且在另一个列表中是否以相同的顺序出现 [英] Determine if all elements in a list are present and in the same order in another list

问题描述

我如何创建一个包含两个列表(list1和list2)的函数sublist()，如果list1是list2的子列表，则返回True，否则返回False.如果list1中的数字以与list1中出现的顺序相同的顺序出现在list2中，则list1是list2的子列表，但不一定是连续的.例如，

How do I create a function sublist() that takes two lists, list1 and list2, and returns True if list1 is a sublist of list2, and False otherwise. list1 is a sublist of list2 if the numbers in list1 appear in list2 in the same order as they appear in list1, but not necessarily consecutively. For example,

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

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

推荐答案

这是使用迭代器在线性时间(和恒定空间)中进行操作的一种方法:

Here's one way to do it in linear time (and constant space) with an iterator:

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语句).如果我们没有足够的元素来查看完整列表，则意味着我们没有匹配项.

Basically it goes through each element of the sublist, and sees if it can find that same element in the part of the complete list it hasn't looked at yet. If it makes it through the entire sublist it means we have a match (hence the else statement on the for loop). If we run out of elements to look at in the complete list, it means we don't have a match.

我已经更新了解决方案，使其可以在Python 3中使用.对于Python 2.5和更早的版本，next(seq)需要替换为seq.next().

I have updated my solution so it works with Python 3. For Python 2.5 and older, next(seq) needs to be replaced with seq.next().

这篇关于确定列表中的所有元素是否都存在并且在另一个列表中是否以相同的顺序出现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！