testing if a list contains a sublist

Alain Ketterlin alain at dpt-info.u-strasbg.fr
Tue Aug 16 17:39:19 CEST 2011


Laszlo Nagy <gandalf at shopzeus.com> writes:

>>>>> def sublist(lst1, lst2):
>> 	s1 = ','.join(map(str, lst1))
>> 	s2 = ','.join(map(str, lst2))
>> 	return False if s2.find(s1)==-1 else True
>>
>> I don't know about best, but it works for the examples given.
>>
> For numbers, it will always work.

I'm not even sure: if str() is locale-sensitive, it may introduce commas
in numbers (I don't know whether str() is locale-sensitive, the doc
doesn't mention anything.)

> But what about
>
> lst1 = [",",",,"]
> lst1 = [",",",",","]

Yes.

It will also fail on nested lists, for fundamental reasons which are
impossible to handle with regexps. (Tough I'm not sure the OP had nested
lists in mind.)

The "brute-force" algorithm given somewhere else in this thread is
probably the way to go, unless the lists are really long, in which case
one of the "string searching" algorithm should be used (I would be
surprised noone has implemented Boyer-Moore or Karp-Rabin).

-- Alain.



More information about the Python-list mailing list