assertion test for program that checks if a list is a sublist from another list

Question

I Have written a small program that should check if a given list is a sublist from another list and returns with True or False:

def is_sublist_of(sublist, given):
    """ Returns whether the sublist is part of the given combination.
    The order of the sublist must also correspond to the order of the
    corresponding part in the given combination."""

    return sublist in [given[i:i+len(sublist)] for i in range(0,len(given)-len(sublist))]

This code is part of an assignment I have to do but one of the given asserts is:

simple_list = [1, 2, 3, 4]
for element in simple_list:
    assert is_sublist_of([element], simple_list)
assert not is_sublist_of([5], simple_list)

And my program fails this test. Does this mean that my program doesn't work in some special cases? Thank you for looking into this.

Answer 1

Yes. You do not generate all sublists: the last one is omitted. If you give given = [1,2,3,4] and sublist = [1], one gets:

>>> given = [1, 2, 3, 4]
>>> sublist = [1]
>>> [given[i:i+len(sublist)] for i in range(0,len(given)-len(sublist))]
[[1], [2], [3]]

(they call this usually an "off by one error").

A fast fix would be:

return sublist in [given[i:i+len(sublist)] for i in range(0,len(given)-len(sublist)+1)]

so with +1 in the range(..).

But a more elegant solution would be:

def is_sublist_of(sublist, given):
    n = len(sublist)
    return any(sublist == given[i:i+n] for i in range(len(given)-n+1))

Here the algorithm will stop from the moment it has found such list and thus not generate all sublists and then check if one of them matches.