如何测试一个列表是否包含另一个列表作为连续的子序列？-IT科技

摘要：问题描述：如何测试一个列表是否包含另一个列表（即它是一个连续的子序列）。假设有一个名为 contains 的函数：contains([1,2], [-1, 0, 1, 2]) # Returns [2, 3] (contains returns [start, end]) contains([1,3], [-...

问题描述：

如何测试一个列表是否包含另一个列表（即它是一个连续的子序列）。假设有一个名为 contains 的函数：

contains([1,2], [-1, 0, 1, 2]) # Returns [2, 3] (contains returns [start, end])
contains([1,3], [-1, 0, 1, 2]) # Returns False
contains([1, 2], [[1, 2], 3]) # Returns False
contains([[1, 2]], [[1, 2], 3]) # Returns [0, 0]

编辑：

contains([2, 1], [-1, 0, 1, 2]) # Returns False
contains([-1, 1, 2], [-1, 0, 1, 2]) # Returns False
contains([0, 1, 2], [-1, 0, 1, 2]) # Returns [1, 3]

解决方案 1：

如果所有项目都是唯一的，则可以使用集合。

>>> items = set([-1, 0, 1, 2])
>>> set([1, 2]).issubset(items)
True
>>> set([1, 3]).issubset(items)
False

解决方案 2：

有一个all()andany()函数可以做到这一点。要检查是否big包含small

result = all(elem in big for elem in small)

检查是否small包含任何元素big

result = any(elem in big for elem in small)

变量结果将是布尔值（TRUE/FALSE）。

解决方案 3：

这是我的版本：

def contains(small, big):
    for i in xrange(len(big)-len(small)+1):
        for j in xrange(len(small)):
            if big[i+j] != small[j]:
                break
        else:
            return i, i+len(small)
    return False

它返回一个元组(start, end+1)，因为我认为这更符合 Python 风格，正如 Andrew Jaffe 在其评论中指出的那样。它不会对任何子列表进行切片，因此应该相当高效。

对于新手来说，一个有趣的点是它在 for 语句中使用了 else 子句——这不是我经常使用的东西，但在这种情况下却非常有用。

这与在字符串中查找子字符串相同，因此对于大型列表，实现类似Boyer-Moore 算法可能会更有效。

注意：如果您使用的是Python3，请更改xrange为range。

解决方案 4：

如果列表真的很大，我谦虚地建议使用Rabin-Karp 算法big。该链接甚至包含几乎可用的 Python 代码。

解决方案 5：

list.index()这是可行的并且相当快，因为它使用内置方法和运算符进行线性搜索==：

def contains(sub, pri):
    M, N = len(pri), len(sub)
    i, LAST = 0, M-N+1
    while True:
        try:
            found = pri.index(sub[0], i, LAST) # find first elem in sub
        except ValueError:
            return False
        if pri[found:found+N] == sub:
            return [found, found+N-1]
        else:
            i = found+1

解决方案 6：

我总结并评估了不同技术所花费的时间

使用的方法有：

def containsUsingStr(sequence, element:list):
    return str(element)[1:-1] in str(sequence)[1:-1]


def containsUsingIndexing(sequence, element:list):
    lS, lE = len(sequence), len(element)
    for i in range(lS - lE + 1):
        for j in range(lE):
            if sequence[i+j] != element[j]: break
        else: return True
    return False


def containsUsingSlicing(sequence, element:list):
    lS, lE = len(sequence), len(element)
    for i in range(lS - lE + 1):
        if sequence[i : i+lE] == element: return True
    return False


def containsUsingAny(sequence:list, element:list):
    lE = len(element)
    return any(element == sequence[i:i+lE] for i in range(len(sequence)-lE+1))

时间分析代码（平均超过 1000 次迭代）：

from time import perf_counter

functions = (containsUsingStr, containsUsingIndexing, containsUsingSlicing, containsUsingAny)
fCount = len(functions)


for func in functions:
    print(str.ljust(f'Function : {func.__name__}', 32), end='   ::   Return Values: ')
    print(func([1,2,3,4,5,5], [3,4,5,5]) , end=', ')
    print(func([1,2,3,4,5,5], [1,3,4,5]))



avg_times = [0]*fCount
for _ in range(1000):
    perf_times = []
    for func in functions:
        startTime = perf_counter()
        func([1,2,3,4,5,5], [3,4,5,5])
        timeTaken = perf_counter()-startTime
        perf_times.append(timeTaken)
        

    for t in range(fCount): avg_times[t] += perf_times[t]

minTime = min(avg_times)
print("

 Ratio of Time of Executions : ", ' : '.join(map(lambda x: str(round(x/minTime, 4)), avg_times)))

输出：

结论：在这种情况下，切片操作被证明是最快的

解决方案 7：

如果我们细化这个问题，测试一个列表是否包含另一个带有序列的列表，那么答案可能是下一行：

def contains(subseq, inseq):
    return any(inseq[pos:pos + len(subseq)] == subseq for pos in range(0, len(inseq) - len(subseq) + 1))

下面是我用来调整这一行代码的单元测试：

https://gist.github.com/anonymous/6910a85b4978daee137f

解决方案 8：

OP 编辑后：

def contains(small, big):
    for i in xrange(1 + len(big) - len(small)):
        if small == big[i:i+len(small)]:
            return i, i + len(small) - 1
    return False

解决方案 9：

这是一个使用列表方法的简单算法：

#!/usr/bin/env python

def list_find(what, where):
    """Find `what` list in the `where` list.

    Return index in `where` where `what` starts
    or -1 if no such index.

    >>> f = list_find
    >>> f([2, 1], [-1, 0, 1, 2])
    -1
    >>> f([-1, 1, 2], [-1, 0, 1, 2])
    -1
    >>> f([0, 1, 2], [-1, 0, 1, 2])
    1
    >>> f([1,2], [-1, 0, 1, 2])
    2
    >>> f([1,3], [-1, 0, 1, 2])
    -1
    >>> f([1, 2], [[1, 2], 3])
    -1
    >>> f([[1, 2]], [[1, 2], 3])
    0
    """
    if not what: # empty list is always found
        return 0
    try:
        index = 0
        while True:
            index = where.index(what[0], index)
            if where[index:index+len(what)] == what:
                return index # found
            index += 1 # try next position
    except ValueError:
        return -1 # not found

def contains(what, where):
    """Return [start, end+1] if found else empty list."""
    i = list_find(what, where)
    return [i, i + len(what)] if i >= 0 else [] #NOTE: bool([]) == False

if __name__=="__main__":
    import doctest; doctest.testmod()

解决方案 10：

最小代码：

def contains(a,b):
    str(a)[1:-1].find(str(b)[1:-1])>=0

解决方案 11：

这是我的答案。此函数将帮助您找出 B 是否是 A 的子列表。时间复杂度为 O(n)。

`def does_A_contain_B(A, B): #remember now A is the larger list
    b_size = len(B)
    for a_index in range(0, len(A)):
        if A[a_index : a_index+b_size]==B:
            return True
    else:
        return False`

解决方案 12：

我尝试让这个过程尽可能的高效。

它使用一个生成器；建议那些不熟悉这些东西的人查看它们的文档和收益表达式的文档。

基本上，它会根据子序列创建一个值生成器，可以通过向其发送真值来重置该生成器。如果重置生成器，它会从的开头再次开始产生结果sub。

然后，它只需将连续的值sequence与生成器的产量进行比较，如果不匹配，则重置生成器。

当生成器用尽值时，即sub在未重置的情况下到达末尾，这意味着我们找到了匹配。

由于它适用于任何序列，因此您甚至可以在字符串上使用它，在这种情况下，它的行为类似于str.find，只是它返回False而不是-1。

进一步说明：我认为返回的元组的第二个值应该符合 Python 标准，通常应该高一个。即"string"[0:2] == "st"。但是规范另有说明，所以这就是它的工作原理。

这取决于这是否是一个通用例程或者是否实现某个特定目标；在后一种情况下，最好实现一个通用例程，然后将其包装在一个函数中，该函数可以根据规范调整返回值。

def reiterator(sub):
    """Yield elements of a sequence, resetting if sent ``True``."""
    it = iter(sub)
    while True:
        if (yield it.next()):
            it = iter(sub)

def find_in_sequence(sub, sequence):
    """Find a subsequence in a sequence.

    >>> find_in_sequence([2, 1], [-1, 0, 1, 2])
    False
    >>> find_in_sequence([-1, 1, 2], [-1, 0, 1, 2])
    False
    >>> find_in_sequence([0, 1, 2], [-1, 0, 1, 2])
    (1, 3)
    >>> find_in_sequence("subsequence",
    ...                  "This sequence contains a subsequence.")
    (25, 35)
    >>> find_in_sequence("subsequence", "This one doesn't.")
    False

    """
    start = None
    sub_items = reiterator(sub)
    sub_item = sub_items.next()
    for index, item in enumerate(sequence):
        if item == sub_item:
            if start is None: start = index
        else:
            start = None
        try:
            sub_item = sub_items.send(start is None)
        except StopIteration:
            # If the subsequence is depleted, we win!
            return (start, index)
    return False

解决方案 13：

我觉得这个很快...

def issublist(subList, myList, start=0):
    if not subList: return 0
    lenList, lensubList = len(myList), len(subList)
    try:
        while lenList - start >= lensubList:
            start = myList.index(subList[0], start)
            for i in xrange(lensubList):
                if myList[start+i] != subList[i]:
                    break
            else:
                return start, start + lensubList - 1
            start += 1
        return False
    except:
        return False

解决方案 14：

a=[[1,2] , [3,4] , [0,5,4]]
print(a.__contains__([0,5,4]))

它提供真实的输出。

a=[[1,2] , [3,4] , [0,5,4]]
print(a.__contains__([1,3]))

它提供了错误的输出。

解决方案 15：

Dave 的回答很好。但我建议采用这种更高效且不使用嵌套循环的实现方式。

def contains(small_list, big_list):
    """
    Returns index of start of small_list in big_list if big_list
    contains small_list, otherwise -1.
    """
    loop = True
    i, curr_id_small= 0, 0
    while loop and i<len(big_list):
        if big_list[i]==small_list[curr_id_small]:
            if curr_id_small==len(small_list)-1:
                loop = False
            else:
                curr_id_small += 1
        else:
            curr_id_small = 0
        i=i+1
    if not loop:
        return i-len(small_list)
    else:
        return -1

解决方案 16：

这是一个简单而有效的函数，用于检查大列表是否按匹配顺序包含小列表：

def contains(big, small):
    i = 0
    for value in big:
        if value == small[i]:
            i += 1
            if i == len(small):
                return True
        else:
            i = 1 if value == small[0] else 0
    return False

用法：

"""
>>> contains([1,2,3,4,5], [2,3,4])
True
>>> contains([4,2,3,2,4], [2,3,4])
False
>>> contains([1,2,3,2,3,2,2,4,3], [2,4,3])
True
"""

解决方案 17：

大多数答案的问题是，它们适用于列表中的唯一项目。如果项目不是唯一的，并且您仍然想知道是否存在交集，则应该对项目进行计数：

from collections import Counter as count

def listContains(l1, l2):
  list1 = count(l1)
  list2 = count(l2)

  return list1&list2 == list1

print( listContains([1,1,2,5], [1,2,3,5,1,2,1]) ) # Returns True
print( listContains([1,1,2,8], [1,2,3,5,1,2,1]) ) # Returns False

您还可以使用以下方法返回交点''.join(list1&list2)

解决方案 18：

这里有一个代码行较少且易于理解的解决方案（或者至少我喜欢这么认为）。

如果您想保持顺序（仅当较小列表在较大列表中以相同的顺序出现时才匹配）：

def is_ordered_subset(l1, l2):
    # First check to see if all element of l1 are in l2 (without checking order)
    if not set(l1).issubset(l2): 
        return False

    length = len(l1)
    # Make sublist of same size than l1
    list_of_sublist = [l2[i:i+length] for i, x in enumerate(l2)]
    #Check if one of this sublist is l1
    return l1 in list_of_sublist

解决方案 19：

你可以使用numpy：

def contains(l1, l2):
   """ returns True if l2 conatins l1 and False otherwise """

   if len(np.intersect1d(l1,l2))==len(l1):
      return = True
   else:
      return = False