在列表中检查子列表

Question

问题是：你需要编写一个名为 isSublist() 的函数，它接受两个参数 (list, sublist) 并返回 1 如果子列表是列表的子列表，否则返回 0。

所以我有我的代码，但是当子列表不在列表中时我得到了 True。请问如何修复这个问题？

 def isSublist(list, sublist):
    for i in range(len(list)-(len(sublist))+1):
        return True
    if sublist==list[i:i+(len(sublist))]:
        return False

样例输入：

list= (0,1,2,3,4,5,6,7,8,9)
isSublist(list, [1,2,3])
output:
True

- user2898221

---

你能提供样例输入和期望输出吗？当你说子列表时，是指像[1,2,3] in [[1,2,3], [5,6,7]]这样的，还是指[1,2,3] in [1,2,3,4,5,6]这样的？ - Steinar Lima

请简要定义什么是列表的子列表。 - pkacprzak

顺序是否重要？您希望两个子列表 [1, 2, 3] 和 [2, 3, 1] 的输出相同吗？ - Steinar Lima

通过子列表，我指的是在列表中[1,2,3,4]是否为列表[1,2]的子列表。如果是，则打印True，否则打印False。 - user2898221

sublist = [2, 1] 呢？如果 list = [1, 1, 2, 2, 3] 和 sublist = [1, 2, 3] 呢？ - Steinar Lima

@SteinarLima 子列表不能是反向的。子列表必须与列表完全相同。 - user2898221

Answer 1

你可以通过获取所有大小与子列表相同的切片并比较相等性来分解它：

def n_slices(n, list_):
    for i in xrange(len(list_) + 1 - n):
        yield list_[i:i+n]

def isSublist(list_, sub_list):
    for slice_ in n_slices(len(sub_list), list_):
        if slice_ == sub_list:
            return True
    return False

为了解决排序问题。按照定义，列表是有序的。如果要忽略排序，可以使用集合（sets）:

def isSubset(list_, sub_list):
    return set(sub_list) <= set(list_)

如果我们需要涵盖重复元素并忽略顺序，那么现在你就进入了多重集合的领域：

def isSubset(list_, sub_list):
    for item in sub_list:
        if sub_list.count(item) > list_.count(item):
            return False
    return True

- John Spong

---

集合有一个 <= 运算符，不需要使用并集。return set(sub_list) <= set(list_) - FogleBird

Answer 2

def isSublist(x, y):
  occ = [i for i, a in enumerate(x) if a == y[0]]
  for b in occ:
      if x[b:b+len(y)] == y:
           print 'YES-- SUBLIST at : ', b
           return True
      else:
           pass
      if len(occ)-1 ==  occ.index(b):
           print 'NO SUBLIST'
           return False

list1 = [1,0,1,1,1,0,0]
list2 = [1,0,1,0,1,0,1]

#should return True
isSublist(list1, [1,1,1])

#Should return False
isSublist(list2, [1,1,1])

- SuperNova

Answer 3

我刚刚为此编写了一份配方（这适用于连续子列表）：

def is_sublist(sublist, superlist):  
    ''''' 
    Checks whether 'sublist' is a sublist of 'superlist'. 
    Both arguments must be typed list or tuple. 
    '''  
    if not isinstance(sublist, (list, tuple)) or not isinstance(sublist, (list,tuple)):  
        raise TypeError("Both 'sublist' and 'superlist' must be lists or tuples.")  
    # Return early if candidate sublist is longer than superlist  
    if len(sublist) > len(superlist):  
        return False  
    else:  
        for chunk in (superlist[i:i+len(sublist)] for i in range(0, len(superlist)-len(sublist)+1)):   
            if chunk == sublist:  
                return True  
        return False

这个想法是使用一个移动的窗口（与候选子列表具有相同的宽度）扫描超级列表，并在每次迭代中检查块和子列表之间的相等性。

这是一种蛮力方法。

- Olivier H

---

抱歉，我没有看到原帖日期和所有现有的答案。我会保留我的答案，因为它的语法和类型检查与其他答案有点不同。 - Olivier H

Answer 4

>>> def isSublist(originallist,sublist,biglist):
    if not sublist:
        return True
    if not biglist:
        return False
    if sublist[0]==biglist[0]:
        return isSublist(originallist,sublist[1:],biglist[1:]) or isSublist(originallist,sublist,biglist[1:])
    return isSublist(originallist,originallist,biglist[1:])

测试输出：

>>> isSublist([1,2,4],[1,2,4],[1,2,3,4])
False
>>> isSublist([1,2,3],[1,2,3],[1,2,3,4])
True
>>> 

针对子列表进行了编辑，而不是子集。虽然不太美观，但可以工作。可以添加一个包装器来避免参数混淆。

def sublist(a,b):
    isSublist(a,a,b)

- C.B.

---

isSublist([1, 2, 4], [1, 2, 3, 4]) 返回 True，但是这是错误的。 - FogleBird

OP没有说明顺序是否重要，所以你不可能如此确定。 - Steinar Lima

子列表，而不是子集。子集将是一个简单的 return set(sublist) <= set(list)。 - FogleBird

这是一个子列表而不是子集。 - user2898221

Answer 5

你的问题之一是，在Python中(0,1,2,3,4,5,6,7,8,9)并不是一个list，而是一个tuple——它本质上是一个不可变（无法更改）的list。此外，你应该避免将程序中的东西命名为内置函数和类型相同的名称，因为有时你需要引用它们，而你自己的定义会隐藏系统提供的定义。

解决这个问题的一个简单方法是在名称末尾添加_，如下所示，它试图将参数转换为list（如果最初不是），它不测试sublist参数的类型，但对于它也可能需要进行类似的检查。

def isSublist(list_, sublist):
    if not isinstance(list_, list):
        list_ = list(list_)
    sublen = len(sublist)
    for i in xrange(len(list_)-sublen+1):
        if list_[i:i+sublen] == sublist:
            return True
    return False

list_ = (0,1,2,3,4,5,6,7,8,9)
print subfunc(list_, [0,1])  # --> True
print subfunc(list_, [1,2,3])  # --> True
print subfunc(list_, [4,6,7])  # --> False
print subfunc(list_, [4,5])  # --> True

- martineau