Checking for sublist in list

问题:

The Question is: You are to write a function, called isSublist(), which takes two arguments (list, sublist) and returns 1 if sublist is a sub-list of list, and 0 otherwise.

So i have my code however I get True when the sublist is not in list. Any suggestions on fixing this please?

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

sample input:

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

回答1:

You can break this up by getting all the slices the size of the sublist, and comparing equality:

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

To cover the issue of ordering. A list is, by definition, ordered. If we want to ignore ordering, you can do sets:

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

If we need to cover repeated elements and ignore ordering, you're now in the realm of multisets:

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

回答2:

>>> 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:])

test output:

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

Edited for sublists, not subset. Uglier, but works. Could add a wrapper to avoid confusion of parameters.

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

回答3:

Part of your problem is that in Python(0,1,2,3,4,5,6,7,8,9)isn't technically alist, it's atuple -- which is essentially a immutable (unchangeable)list. Also, you should avoid naming things in your program the same as built-in functions and types, because occasionally you need to reference them and your own definition would hide the ones provided by the system.

One easy way to get around this is to just appending an_to the end of the name, as done in the following which tries to turn convert the argument into alistif it isn't one initially. It doesn't test the type of thesublist argument, but a similar check might be appropriate for it, too.

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

回答4:

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])

回答5:

I've just written a recipe for this (this works for contiguous sublist):

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

The idea is to have a shifting window (having the same width as the candidate sublist) scan the superlist and check for equality between the chunk and the sublist at each iteration.

That's a brute force method.