检查列表是否是子列表

I need to check if list1 is a sublist of list2 (True; if every integer in list2 that is common with list1 is in the same order of indexes as in list1)

我需要检查list1是否是list2的子列表(True;如果清单2中与list1相同的每个整数的索引顺序与清单1相同)

def sublist(lst1,lst2):
    for i in range(len(lst1)):
        if lst1[i] not in lst2:
            return False
        for j in range(len(lst2)):
            if (lst1[j] in lst2) and (lst2.index(lst1[i+1]) > lst2.index(lst1[i])):
                return True

Can anybody help me... why isn't this working?

谁能帮我…为什么这不是工作吗?

9 个解决方案

#1

i need to check if list1 is a sublist to list2 (True; if every integer in list2 that is common with list1 is in the same order of indexes as in list1)

我需要检查列表1是否是列表2的子列表(True;如果清单2中与list1相同的每个整数的索引顺序与清单1相同)

Your code isn't working because as soon as a list element in ls1 doesn't occur in ls2 it will return False immediately.

您的代码不起作用，因为ls1中的list元素在ls2中没有出现，它将立即返回False。

This creates two lists that contain only the common elements (but in their original order) and then returns True when they are the same:

这将创建两个只包含公共元素(但按其原始顺序)的列表，然后在它们相同时返回True:

def sublist(lst1, lst2):
   ls1 = [element for element in lst1 if element in lst2]
   ls2 = [element for element in lst2 if element in lst1]
   return ls1 == ls2

edit: A memory-efficient variant:

编辑:节约内存变体:

def sublist(ls1, ls2):
    '''
    >>> sublist([], [1,2,3])
    True
    >>> sublist([1,2,3,4], [2,5,3])
    True
    >>> sublist([1,2,3,4], [0,3,2])
    False
    >>> sublist([1,2,3,4], [1,2,5,6,7,8,5,76,4,3])
    False
    '''
    def get_all_in(one, another):
        for element in one:
            if element in another:
                yield element

    for x1, x2 in zip(get_all_in(ls1, ls2), get_all_in(ls2, ls1)):
        if x1 != x2:
            return False

    return True

#2

Another way that we do this is with collections.Counter. @L3viathan's second answer is the most efficient and fastest way to do it.

另一种方法是用collection。counter。@L3viathan给出的第二个答案是最有效、最快的方法。

def sublist1(lst1, lst2):
    ls1 = [element for element in lst1 if element in lst2]
    ls2 = [element for element in lst2 if element in lst1]
    return ls1 == ls2


def sublist2(lst1, lst2):
    def get_all_in(one, another):
        for element in one:
            if element in another:
                yield element
    for x1, x2 in zip(get_all_in(lst1, lst2), get_all_in(lst2, lst1)):
        if x1 != x2:
            return False
    return True


def sublist3(lst1, lst2):
    from collections import Counter
    c1 = Counter(lst1)
    c2 = Counter(lst2)
    for item, count in c1.items():
        if count > c2[item]:
            return False
    return True


l1 = ["a", "b", "c", "c", "c", "d", "e"]
l2 = ["c", "a", "c", "b", "c", "c", "d", "d", "f", "e"]

s1 = lambda: sublist1(l1, l2)
s2 = lambda: sublist2(l1, l2)
s3 = lambda: sublist3(l1, l2)

from timeit import Timer
t1, t2, t3 = Timer(s1), Timer(s2), Timer(s3)
print(t1.timeit(number=10000))  # => 0.034193423241588035
print(t2.timeit(number=10000))  # => 0.012621842119714115
print(t3.timeit(number=10000))  # => 0.12714286673722477

His 2nd way is faster by an order of magnitude, but I wanted to mention the Counter variant because of its prevalence and usage outside of this scenario.

他的第二种方法速度快了一个数量级，但是我想提一下反变量，因为它在这个场景之外的流行和使用。

#3

Memory efficient solution based on M. Morgan's answer. Takes into consideration that in order to be a sublist, the sublist must be found in the same order in the super list.

基于M. Morgan的答案的内存效率解决方案。考虑到要成为子列表，必须在超级列表中以相同的顺序找到子列表。

Variable k keeps track of the length of matched characters. When this matches the length of our sublist we can return true.

变量k跟踪匹配字符的长度。当它与子列表的长度匹配时，我们可以返回true。

Variable s keeps track of the starting value. I keep track of this so that a test case like sublist(["1", "1", "2"],["0", "1", "1", "1", "2", "1", "2"]) with extraneous repeats of the first entry don't affect the current index reset when unmatched. Once the starting value changes s becomes irrelevant so this case does not fire in the middle of a pattern.

变量s跟踪起始值。我记录下了这样一个测试用例，如子列表([1]、“1”、“2”)、[“0”、“1”、“1”、“1”、“2”、“1”、“2”)，与第一个条目无关的重复，在没有匹配的情况下，不会影响当前的索引重置。一旦开始值的变化变得无关紧要，那么这个例子就不会在模式的中间触发。

def sublist(sublist, lst):
    if not isinstance(sublist, list):
        raise ValueError("sublist must be a list")
    if not isinstance(lst, list):
        raise ValueError("lst must be a list")

    sublist_len = len(sublist)
    k=0
    s=None

    if (sublist_len > len(lst)):
        return False
    elif (sublist_len == 0):
        return True

    for x in lst:
        if x == sublist[k]:
            if (k == 0): s = x
            elif (x != s): s = None
            k += 1
            if k == sublist_len:
                return True
        elif k > 0 and sublist[k-1] != s:
            k = 0

    return False

#4

I found the above all found ['a','b','d'] to be a sublist of ['a','b','c','e','d'], which may not be true in spite of all of the elements of the sublist being present in the list. So to maintain the order and I came up with:

我发现上面发现的[a]、[b]、[d]都是[a]、[b]、[b]、[c]、[e]、[d]的子列表，尽管子列表中的所有元素都在列表中，但可能不是这样。为了维持秩序，我想到

def sublist4(sublist,lst):
    #Define an temp array to populate 
    sub_list=[]
    comparable_sublist=[]
    #Define two constants to iterate in the while loop
    i=0
    k=0
    #Loop the length of lst
    while i < len(lst):
        #If the element is in the sublist append to temp array, 
        if k < len(sublist) and lst[i] == sublist[k]:
            sub_list.append(lst[i])
            #set a comparable array to the value of temp array
            comparable_sublist = sub_list
            k += 1
            #If the comparable array is the same as the sublist, break
            if len(comparable_sublist) == len(sublist):
                break

        #If the element is not in the sublist, reset temp array
        else:
            sub_list = []


        i += 1

    return comparable_sublist == sublist

Whilst this isn't very memory efficient, I find it works quite well with small lists.

虽然这并不是非常有效的内存，但我发现它对于小列表非常有效。

#5

Its easy with iterators.

与迭代器的简单。

>>> a = [0,1,2]
>>> b = [item for item in range(10)]
>>> b
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> a
[0, 1, 2]
>>> [False, True][set([item in b for item in a]) == set([True])]
True
>>> a = [11, 12, 13]
>>> [False, True][set([item in b for item in a]) == set([True])]
False

#6

An easy way to check if all elements of a list are in other one is converting both to sets:

一种检查列表中所有元素是否在其他元素中的简单方法是将它们转换为集合:

def sublist(lst1, lst2):
    return set(lst1) <= set(lst2)

#7

def sublist(l1,l2):
    s1=" ".join(str(i) for i in l1)
    s2=" ".join(str(i) for i in l2)
    if s1 in s2:
        return True
    else:
        return False

#8

Try this one!! sublist y is not missing the sequence of list x.

试试这个! !子列表y并不缺少列表x的序列。

x= list

x =列表

y= sublist

y =子表

if ([i for i,j in enumerate(y) for k,l in enumerate(x) if i == k and j!=l]):
    print("True")
else:
    print("False")

#9

Another easy way is to use list comprehension And use the built-in function all to verify that all items in list1 are contained in list2.

另一种简单的方法是使用列表理解并使用内置函数来验证list1中的所有项都包含在list2中。

Example:

例子:

list1 = ['1','2']
list2 = ['1','2',3]

all(i in list2 for i in list1)