Re: testing if a list contains a sublist
On Mon, Aug 15, 2011 at 4:26 PM, Johannes dajo.m...@web.de wrote: hi list, what is the best way to check if a given list (lets call it l1) is totally contained in a second list (l2)? for example: l1 = [1,2], l2 = [1,2,3,4,5] - l1 is contained in l2 l1 = [1,2,2,], l2 = [1,2,3,4,5] - l1 is not contained in l2 l1 = [1,2,3], l2 = [1,3,5,7] - l1 is not contained in l2 my problem is the second example, which makes it impossible to work with sets insteads of lists. But something like set.issubset for lists would be nice. greatz Johannes -- http://mail.python.org/mailman/listinfo/python-list Probably not the most efficient way, but I wanted to mention it: from difflib import SequenceMatcher def list_in(a, b): '''Is a completely contained in b?''' matcher = SequenceMatcher(a=a, b=b) m = matcher.find_longest_match(0, len(a), 0, len(b)) return m.size == len(a) Cheers, ~Simon -- http://mail.python.org/mailman/listinfo/python-list
Re: testing if a list contains a sublist
Johannes wrote: hi list, what is the best way to check if a given list (lets call it l1) is totally contained in a second list (l2)? [...] For anyone interested, here's a pair of functions that implement sub-sequence testing similar to str.find and str.rfind: http://code.activestate.com/recipes/577850-search-sequences-for-sub-sequence/ -- Steven -- http://mail.python.org/mailman/listinfo/python-list
Re: testing if a list contains a sublist
On Tue, 16 Aug 2011 09:57:57 -0400, John Posner wrote: How about using Python's core support for == on list objects: for i in range(alist_sz - slist_sz + 1): if slist == alist[i:i+slist_sz]: return True This is bound to be asymptotically O(alist_sz * slist_sz), even if the constant factor is reduced by use of ==. Boyer-Moore and regexps are asymptotically O(alist_sz). However, the setup costs are much higher, so you might need alist_sz to be very large before they win out. -- http://mail.python.org/mailman/listinfo/python-list
Re: testing if a list contains a sublist
On Se shanbe 25 Mordad 1390 01:26:54 Johannes wrote:
hi list,
what is the best way to check if a given list (lets call it l1) is
totally contained in a second list (l2)?
for example:
l1 = [1,2], l2 = [1,2,3,4,5] - l1 is contained in l2
l1 = [1,2,2,], l2 = [1,2,3,4,5] - l1 is not contained in l2
l1 = [1,2,3], l2 = [1,3,5,7] - l1 is not contained in l2
my problem is the second example, which makes it impossible to work with
sets insteads of lists. But something like set.issubset for lists would
be nice.
greatz Johannes
Hope best answer is found so far. for easy answer, i prefer to use Python
`==' operator instead of inner loop.
l=[1,2,3,4,5]
s=[1,2,2]
sc=len(s)
for c in xrange(len(l)-sc+1):
if l[c:sc+c] == s:
print ( 'found at {0}'.format(c) )
break
Since sub-lists memory will be garbage collected, there is no problem in
memory usage, but in time needed for constructing new slice, there is.
--
Amir Ghassemi Nasr (Reith)
GPG ID: 371035B4 (http://46.4.214.112/~reith/reith.asc)
GPG Fingerprint: 18E6 CF11 BE80 F541 DC68 B6AF 9373 DE72 3710 35B4
signature.asc
Description: This is a digitally signed message part.
--
http://mail.python.org/mailman/listinfo/python-list
Re: testing if a list contains a sublist
On Aug 15, 4:26 pm, Johannes dajo.m...@web.de wrote: hi list, what is the best way to check if a given list (lets call it l1) is totally contained in a second list (l2)? for example: l1 = [1,2], l2 = [1,2,3,4,5] - l1 is contained in l2 l1 = [1,2,2,], l2 = [1,2,3,4,5] - l1 is not contained in l2 l1 = [1,2,3], l2 = [1,3,5,7] - l1 is not contained in l2 my problem is the second example, which makes it impossible to work with sets insteads of lists. But something like set.issubset for lists would be nice. greatz Johannes My best guess: from collections import Counter def contains(alist, sublist): alist = Counter(alist) for k in sublist: try: alist[k] -= 1 if alist[k] 0: return False except KeyError: return False return True 'Counter' being better understood as 'Multiset'. If m = len(alist) and n = len(sublist), looks to be roughly O(m+n). Cheers - Chas -- http://mail.python.org/mailman/listinfo/python-list
Re: testing if a list contains a sublist
On Aug 15, 4:26 pm, Johannes dajo.m...@web.de wrote: hi list, what is the best way to check if a given list (lets call it l1) is totally contained in a second list (l2)? for example: l1 = [1,2], l2 = [1,2,3,4,5] - l1 is contained in l2 l1 = [1,2,2,], l2 = [1,2,3,4,5] - l1 is not contained in l2 l1 = [1,2,3], l2 = [1,3,5,7] - l1 is not contained in l2 my problem is the second example, which makes it impossible to work with sets insteads of lists. But something like set.issubset for lists would be nice. greatz Johannes My best guess: from collections import Counter def contains(alist, sublist): alist = Counter(alist) for k in sublist: try: alist[k] -= 1 if alist[k] 0: return False except KeyError: return False return True 'Counter' being better understood as 'Multiset'. If m = len(alist) and n = len(sublist), looks to be roughly O(m+n). Cheers - Chas -- http://mail.python.org/mailman/listinfo/python-list
Re: testing if a list contains a sublist
On Aug 15, 4:26 pm, Johannes dajo.m...@web.de wrote: hi list, what is the best way to check if a given list (lets call it l1) is totally contained in a second list (l2)? for example: l1 = [1,2], l2 = [1,2,3,4,5] - l1 is contained in l2 l1 = [1,2,2,], l2 = [1,2,3,4,5] - l1 is not contained in l2 l1 = [1,2,3], l2 = [1,3,5,7] - l1 is not contained in l2 my problem is the second example, which makes it impossible to work with sets insteads of lists. But something like set.issubset for lists would be nice. greatz Johannes My best guess: from collections import Counter def contains(alist, sublist): alist = Counter(alist) for k in sublist: try: alist[k] -= 1 if alist[k] 0: return False except KeyError: return False return True 'Counter' being better understood as 'Multiset'. If m = len(alist) and n = len(sublist), looks to be roughly O(m+n). Cheers - Chas -- http://mail.python.org/mailman/listinfo/python-list
Re: testing if a list contains a sublist
hi list, what is the best way to check if a given list (lets call it l1) is totally contained in a second list (l2)? for example: l1 = [1,2], l2 = [1,2,3,4,5] - l1 is contained in l2 l1 = [1,2,2,], l2 = [1,2,3,4,5] - l1 is not contained in l2 l1 = [1,2,3], l2 = [1,3,5,7] - l1 is not contained in l2 my problem is the second example, which makes it impossible to work with sets insteads of lists. But something like set.issubset for lists would be nice. greatz Johannes Fastest, error-free and simplest solution is to use sets: l1 = [1,2] l2 = [1,2,3,4,5] set(l1)-set(l2) set([]) set(l2)-set(l1) set([3, 4, 5]) Although with big lists, this is not very memory efficient. But I must tell you, sometimes I use this method for lists with millions of integers, and it is very fast and reliable, and memory is not a concern for me, at least - some million integers will fit into a few MB of memory. Read the docs about set operators for creating union, symmetric difference etc. Best, Laszlo -- http://mail.python.org/mailman/listinfo/python-list
Re: testing if a list contains a sublist
Laszlo Nagy gand...@shopzeus.com wrote:
Fastest, error-free and simplest solution is to use sets:
l1 = [1,2]
l2 = [1,2,3,4,5]
set(l1)-set(l2)
set([])
set(l2)-set(l1)
set([3, 4, 5])
Error-free? Not given the stated requirements:
l1 = [1,2,2,], l2 = [1,2,3,4,5] - l1 is not contained in l2
l1 = [1,2,2]
l2 = [1,2,3,4,5]
set(l1)-set(l2)
set()
set(l2)-set(l1)
{3, 4, 5}
As you can see, using sets provides the exact same result for a non-
contained sub-list as it does for your valid example. The list
[1,2,2,2,2,2,2,2,2] is clearly not contained with [1,2,3], but your
code would say it is.
Similarly, [9,8,7] would appear to be a sub-list of [5,6,7,8,9],
something I'd also considered to be false in this instance.
(My apologies if this is a double-up, the original post hasn't
appeared yet)
--
http://mail.python.org/mailman/listinfo/python-list
Re: testing if a list contains a sublist
On Aug 16, 4:51 pm, Laszlo Nagy gand...@shopzeus.com wrote:
hi list,
what is the best way to check if a given list (lets call it l1) is
totally contained in a second list (l2)?
for example:
l1 = [1,2], l2 = [1,2,3,4,5] - l1 is contained in l2
l1 = [1,2,2,], l2 = [1,2,3,4,5] - l1 is not contained in l2
l1 = [1,2,3], l2 = [1,3,5,7] - l1 is not contained in l2
my problem is the second example, which makes it impossible to work with
sets insteads of lists. But something like set.issubset for lists would
be nice.
greatz Johannes
Fastest, error-free and simplest solution is to use sets:
l1 = [1,2]
l2 = [1,2,3,4,5]
set(l1)-set(l2)
set([])
set(l2)-set(l1)
set([3, 4, 5])
Error free? Consider this stated requirement:
l1 = [1,2,2,], l2 = [1,2,3,4,5] - l1 is not contained in l2
l1 = [1,2,2]
l2 = [1,2,3,4,5]
set(l1)-set(l2)
set()
set(l2)-set(l1)
{3, 4, 5}
So set([1,2]) == set([1,2,2]), despite [1,2,2] not being a sublist of
the original.
It also completely ignores list order, which would make [9,8,7] a
sublist of [5,6,7,8,9].
--
http://mail.python.org/mailman/listinfo/python-list
Re: testing if a list contains a sublist
On Aug 15, 11:51 pm, Laszlo Nagy gand...@shopzeus.com wrote: hi list, what is the best way to check if a given list (lets call it l1) is totally contained in a second list (l2)? for example: l1 = [1,2], l2 = [1,2,3,4,5] - l1 is contained in l2 l1 = [1,2,2,], l2 = [1,2,3,4,5] - l1 is not contained in l2 l1 = [1,2,3], l2 = [1,3,5,7] - l1 is not contained in l2 my problem is the second example, which makes it impossible to work with sets insteads of lists. But something like set.issubset for lists would be nice. greatz Johannes Fastest, error-free and simplest solution is to use sets: l1 = [1,2] l2 = [1,2,3,4,5] set(l1)-set(l2) set([]) set(l2)-set(l1) set([3, 4, 5]) This approach fails the OP's desires when l1 = [1,2,2,] l2 = [1,2,3,4,5] The OP explicitly desires 'l2 contains l1' to be false in that case. Cheers - Chas -- http://mail.python.org/mailman/listinfo/python-list
Re: testing if a list contains a sublist
Johannes wrote: what is the best way to check if a given list (lets call it l1) is totally contained in a second list (l2)? for example: l1 = [1,2], l2 = [1,2,3,4,5] - l1 is contained in l2 l1 = [1,2,2,], l2 = [1,2,3,4,5] - l1 is not contained in l2 l1 = [1,2,3], l2 = [1,3,5,7] - l1 is not contained in l2 my problem is the second example, which makes it impossible to work with sets insteads of lists. But something like set.issubset for lists would be nice. Would [1, 2, 1] be contained in [1, 1, 2]? You have received an answer that assumes yes and another that assume no. -- http://mail.python.org/mailman/listinfo/python-list
Re: testing if a list contains a sublist
Error free? Consider this stated requirement: l1 = [1,2,2,], l2 = [1,2,3,4,5] - l1 is not contained in l2 If you look it the strict way, containment relation for lists is meant this way: l1 = [] l2 = [1,l1,2] # l2 CONTAINS l1 But you are right, I was wrong. So let's clarify what the OP wants! For example: l1 = [1,2,2,], l2 = [2,1,2,3,4,5] What is the relation between these two lists? Does l2 contain l1 or not? In other words, is this containment relation interpreted on multisets not considering the order of the items? It also completely ignores list order, which would make [9,8,7] a sublist of [5,6,7,8,9]. Exactly. However, from the original post of Johannes it was not clear if the order of the elements counts or not. If It this is interpreted as a multiset relation, it would be easier to use collections.Counter. If the order of elements is important then he can start with a Boyer-Moore algorithm. Best, Laszlo -- http://mail.python.org/mailman/listinfo/python-list
Re: testing if a list contains a sublist
On Tue, 16 Aug 2011 12:12 pm Steven D'Aprano wrote: On Tue, 16 Aug 2011 09:26 am Johannes wrote: hi list, what is the best way to check if a given list (lets call it l1) is totally contained in a second list (l2)? This is not the most efficient algorithm, but for short lists it should be plenty fast enough: Nope, sorry, that was buggy. Here's another version which should be accurate but may be slower. def search(source, target, start=0, end=None): Naive search for target in source. m = len(source) n = len(target) if end is None: end = m if n == 0 or m n: return None for i in range(start, end-n+1): if source[i:i+n] == target: return i return None -- Steven -- http://mail.python.org/mailman/listinfo/python-list
Re: testing if a list contains a sublist
Am 16.08.2011 09:44, schrieb Peter Otten: Johannes wrote: what is the best way to check if a given list (lets call it l1) is totally contained in a second list (l2)? for example: l1 = [1,2], l2 = [1,2,3,4,5] - l1 is contained in l2 l1 = [1,2,2,], l2 = [1,2,3,4,5] - l1 is not contained in l2 l1 = [1,2,3], l2 = [1,3,5,7] - l1 is not contained in l2 my problem is the second example, which makes it impossible to work with sets insteads of lists. But something like set.issubset for lists would be nice. Would [1, 2, 1] be contained in [1, 1, 2]? You have received an answer that assumes yes and another that assume no. yes it should be contained in the other one. I just work with sorted lists, so i did not think about this case. geatz Johannes -- http://mail.python.org/mailman/listinfo/python-list
Re: testing if a list contains a sublist
On Tue, 16 Aug 2011 04:14 pm ChasBrown wrote: On Aug 15, 4:26 pm, Johannes dajo.m...@web.de wrote: hi list, what is the best way to check if a given list (lets call it l1) is totally contained in a second list (l2)? for example: l1 = [1,2], l2 = [1,2,3,4,5] - l1 is contained in l2 l1 = [1,2,2,], l2 = [1,2,3,4,5] - l1 is not contained in l2 l1 = [1,2,3], l2 = [1,3,5,7] - l1 is not contained in l2 my problem is the second example, which makes it impossible to work with sets insteads of lists. But something like set.issubset for lists would be nice. greatz Johannes My best guess: from collections import Counter There's no reason to think that the Original Poster wants a multiset based solution. He asked about lists and sublists. That's a standard term, like substring: 12 is a substring of 01234. 21 and 13 are not. [1, 2] is a sublist of [0, 1, 2, 3, 4]. [2, 1] and [1, 3] are not. Since lists are ordered, so are sublists. If the OP does want a solution that ignores order, then he needs to describe his problem better. -- Steven -- http://mail.python.org/mailman/listinfo/python-list
Re: testing if a list contains a sublist
Johannes wrote: Am 16.08.2011 09:44, schrieb Peter Otten: Johannes wrote: what is the best way to check if a given list (lets call it l1) is totally contained in a second list (l2)? for example: l1 = [1,2], l2 = [1,2,3,4,5] - l1 is contained in l2 l1 = [1,2,2,], l2 = [1,2,3,4,5] - l1 is not contained in l2 l1 = [1,2,3], l2 = [1,3,5,7] - l1 is not contained in l2 my problem is the second example, which makes it impossible to work with sets insteads of lists. But something like set.issubset for lists would be nice. Would [1, 2, 1] be contained in [1, 1, 2]? You have received an answer that assumes yes and another that assume no. yes it should be contained in the other one. I just work with sorted lists, so i did not think about this case. geatz Johannes For short lists l1: pairs = [ ... ([1,2], [1,2,3,4,5]), ... ([1,2,2,], [1,2,3,4,5]), ... ([1,2,3], [1,3,5,7])] for l1, l2 in pairs: ... contained = all(l1.count(item) = l2.count(item) for item in set(l1)) ... print l1, [not in, in][contained], l2 ... [1, 2] in [1, 2, 3, 4, 5] [1, 2, 2] not in [1, 2, 3, 4, 5] [1, 2, 3] not in [1, 3, 5, 7] -- http://mail.python.org/mailman/listinfo/python-list
Re: testing if a list contains a sublist
On Tue, 16 Aug 2011 01:26:54 +0200, Johannes wrote: what is the best way to check if a given list (lets call it l1) is totally contained in a second list (l2)? Best is subjective. AFAIK, the theoretically-optimal algorithm is Boyer-Moore. But that would require a fair amount of code, and Python isn't a particularly fast language, so you're likely to get better results if you can delegate most of the leg-work to a native library (along the lines of Roy's suggestion of using regexps). -- http://mail.python.org/mailman/listinfo/python-list
Re: testing if a list contains a sublist
Roy Smith r...@panix.com writes: what is the best way to check if a given list (lets call it l1) is totally contained in a second list (l2)? [...] import re def sublist(l1, l2): s1 = ''.join(map(str, l1)) s2 = ''.join(map(str, l2)) return re.search(s1, s2) This is complete nonsense (try it on [12] and [1,2]). The original problem is string searching (where strings here are sequences of numbers instead of characters). See http://en.wikipedia.org/wiki/String_searching_algorithm for any algorithm (Rabin-Karp seems appropriate to me). -- Alain. -- http://mail.python.org/mailman/listinfo/python-list
Re: testing if a list contains a sublist
In article 8739h18rzj@dpt-info.u-strasbg.fr, Alain Ketterlin al...@dpt-info.u-strasbg.fr wrote: Roy Smith r...@panix.com writes: what is the best way to check if a given list (lets call it l1) is totally contained in a second list (l2)? [...] import re def sublist(l1, l2): s1 = ''.join(map(str, l1)) s2 = ''.join(map(str, l2)) return re.search(s1, s2) This is complete nonsense (try it on [12] and [1,2]). No, it's not complete nonsense, it works just fine for the limited data set the OP presented :-) Of course, you are correct that it only works for single-digit integers, hence my running and ducking comment. The original problem is string searching (where strings here are sequences of numbers instead of characters). See http://en.wikipedia.org/wiki/String_searching_algorithm for any algorithm (Rabin-Karp seems appropriate to me). Yes, of course this is fundamentally a string searching problem. The problem is that while Python comes with an excellent tool for doing these kinds of string searches, its domain is limited to, as you pointed out, character strings. However, for the limited data the OP presented, there is a trivial way to map the original data domain (single digit integers) into the domain the re library knows about (character strings). My answer may be a sucky general-purpose solution, but it's also a neat hack, and sometimes a neat hack is what you need. It also occurs to me that this hack could be expanded a bit to handle a much larger input domain. If you had sequences of arbitrary (but hashable) objects, you could map this into a unicode string where each character is the 32-bit hash of of the corresponding input object, then run the regex search on that. In theory, it should work. In practice, I can see a few potential problems: 1) You might have to carefully craft your hash function to avoid magic unicode values like null or BOM. No biggie there. 2) Hash collisions can lead to false positives, so you need to filter those out with a subsequent linear comparison step. Of course, this is true of any kind of hash lookup. No biggie there either. 3) While the re module is advertised to work on unicode data, I have no idea how efficient it is on arbitrary values. I wouldn't be too surprised if it's tuned for mostly ascii utf-8 and performance suffers on completely random strings. If its first step is to transcode to utf-32 internally, I expect it would work just fine, but it would take some experimentation (or reading of the source code) to validate this assumption. -- http://mail.python.org/mailman/listinfo/python-list
Re: testing if a list contains a sublist
On 2:59 PM, Nobody wrote: On Tue, 16 Aug 2011 01:26:54 +0200, Johannes wrote: what is the best way to check if a given list (lets call it l1) is totally contained in a second list (l2)? Best is subjective. AFAIK, the theoretically-optimal algorithm is Boyer-Moore. But that would require a fair amount of code, and Python isn't a particularly fast language, so you're likely to get better results if you can delegate most of the leg-work to a native library (along the lines of Roy's suggestion of using regexps). How about using Python's core support for == on list objects: def contains(alist, slist): predicate: is *slist* a sublist of *alist*? alist_sz = len(alist) slist_sz = len(slist) # special cases if slist_sz == 0: return True # empty list *is* a sublist elif slist_sz == alist_sz and alist == slist: return True elif slist_sz alist_sz: return False # standard case for i in range(alist_sz - slist_sz + 1): if slist == alist[i:i+slist_sz]: return True # fell through for loop: no match found return False -John -- http://mail.python.org/mailman/listinfo/python-list
Re: testing if a list contains a sublist
On 2:59 PM, Nobody wrote: On Tue, 16 Aug 2011 01:26:54 +0200, Johannes wrote: what is the best way to check if a given list (lets call it l1) is totally contained in a second list (l2)? Best is subjective. AFAIK, the theoretically-optimal algorithm is Boyer-Moore. But that would require a fair amount of code, and Python isn't a particularly fast language, so you're likely to get better results if you can delegate most of the leg-work to a native library (along the lines of Roy's suggestion of using regexps). How about using Python's core support for == on list objects: def contains(alist, slist): predicate: is *slist* a sublist of *alist*? alist_sz = len(alist) slist_sz = len(slist) # special cases if slist_sz == 0: return True # empty list *is* a sublist elif slist_sz == alist_sz and alist == slist: return True elif slist_sz alist_sz: return False # standard case for i in range(alist_sz - slist_sz + 1): if slist == alist[i:i+slist_sz]: return True # fell through for loop: no match found return False -John -- http://mail.python.org/mailman/listinfo/python-list
Re: testing if a list contains a sublist
On Aug 16, 8:23 am, Alain Ketterlin al...@dpt-info.u-strasbg.fr wrote: Roy Smith r...@panix.com writes: what is the best way to check if a given list (lets call it l1) is totally contained in a second list (l2)? [...] import re def sublist(l1, l2): s1 = ''.join(map(str, l1)) s2 = ''.join(map(str, l2)) return re.search(s1, s2) This is complete nonsense (try it on [12] and [1,2]). The original problem is string searching (where strings here are sequences of numbers instead of characters). See http://en.wikipedia.org/wiki/String_searching_algorithm for any algorithm (Rabin-Karp seems appropriate to me). -- Alain. That can be easily fixed: def sublist(lst1, lst2): s1 = ','.join(map(str, lst1)) s2 = ','.join(map(str, lst2)) return False if s2.find(s1)==-1 else True sublist([1,2],[1,2,3,4,5]) True sublist([1,2,2],[1,2,3,4,5]) False sublist([1,2,3],[1,3,5,7]) False sublist([12],[1,2]) False I don't know about best, but it works for the examples given. -- http://mail.python.org/mailman/listinfo/python-list
Re: testing if a list contains a sublist
That can be easily fixed: 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. But what about lst1 = [] lst1 = [,] -- http://mail.python.org/mailman/listinfo/python-list
Re: testing if a list contains a sublist
Am 16.08.2011 10:00, schrieb Laszlo Nagy:
Error free? Consider this stated requirement:
l1 = [1,2,2,], l2 = [1,2,3,4,5] - l1 is not contained in l2
If you look it the strict way, containment relation for lists is meant
this way:
l1 = []
l2 = [1,l1,2] # l2 CONTAINS l1
But you are right, I was wrong. So let's clarify what the OP wants!
For example:
l1 = [1,2,2,], l2 = [2,1,2,3,4,5]
I dont care about this case, because all list are ordered for me.
I've chosen the following solution
def _list_contained_in_list(l1,l2):
d1 = {}
d2 = {}
for i in l1:
if i in d1:
d1[i] += 1
else:
d1[i] = 1
for i in l2:
if i in d2:
d2[i] += 1
else:
d2[i] = 1
if not all([k in d2.keys() for k in d1.keys()]):
return false
return all([d1[i] = d2[i] for i in d1])
greatz Johannes
--
http://mail.python.org/mailman/listinfo/python-list
Re: testing if a list contains a sublist
Laszlo Nagy gand...@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. -- http://mail.python.org/mailman/listinfo/python-list
Re: testing if a list contains a sublist
On 16/08/2011 00:26, Johannes wrote: hi list, what is the best way to check if a given list (lets call it l1) is totally contained in a second list (l2)? for example: l1 = [1,2], l2 = [1,2,3,4,5] - l1 is contained in l2 l1 = [1,2,2,], l2 = [1,2,3,4,5] - l1 is not contained in l2 l1 = [1,2,3], l2 = [1,3,5,7] - l1 is not contained in l2 my problem is the second example, which makes it impossible to work with sets insteads of lists. But something like set.issubset for lists would be nice. Here's my solution, using the Counter class: from collections import Counter c1 = Counter([1,2]) c2 = Counter([1,2,3,4,5]) (c1 c2) == c1 True c1 = Counter([1,2,2,]) c2 = Counter([1,2,3,4,5]) (c1 c2) == c1 False c1 = Counter([1,2,3]) c2 = Counter([1,3,5,7]) (c1 c2) == c1 False -- http://mail.python.org/mailman/listinfo/python-list
Re: testing if a list contains a sublist
On 2011-08-16, nn prueba...@latinmail.com wrote: That can be easily fixed: def sublist(lst1, lst2): s1 = ','.join(map(str, lst1)) s2 = ','.join(map(str, lst2)) return False if s2.find(s1)==-1 else True sublist([1,2,3],[1,2,3,4,5]) True sublist([1,2,2],[1,2,3,4,5]) False sublist([1,2,3],[1,3,5,7]) False sublist([12],[1,2]) False String conversion is risky: sublist(['1,2', '3,4'], [1, 2, 3, 4]) True Since we're bike-shedding, here's my entry. It's not clear to me if accepting iterables rather than lists is a win, but I thought, Why not be general if the implementation is easy? def is_subseq_of(x, y): rReturn True if the elements in iterable x are found contiguously in iterable y. is_subseq_of([], []) True is_subseq_of([], [1, 2, 3]) True is_subseq_of([1], [1, 2, 3]) True is_subseq_of([1], []) False is_subseq_of([4, 5], [1, 2, 3, 4, 5]) True is_subseq_of([1, 2], [1, 3, 2]) False is_subseq_of([2, 3], [1, 2, 3, 4]) True is_subseq_of([1, 2, 2], [1, 2, 3, 4, 5]) False is_subseq_of([1, 2], [1, 2]) True is_subseq_of([1, 2, 3], [1, 2]) False is_subseq_of(['1,2', '3,4'], [1, 2, 3, 4]) False x = tuple(x) ix = 0 lenx = len(x) if lenx == 0: return True for elem in y: if x[ix] == elem: ix += 1 else: ix = 0 if ix == lenx: return True return False if __name__ == '__main__': import doctest doctest.testmod() -- Neil Cerutti -- http://mail.python.org/mailman/listinfo/python-list
Re: testing if a list contains a sublist
On Aug 16, 1:37 am, Steven D'Aprano steve +comp.lang.pyt...@pearwood.info wrote: On Tue, 16 Aug 2011 04:14 pm ChasBrown wrote: On Aug 15, 4:26 pm, Johannes dajo.m...@web.de wrote: hi list, what is the best way to check if a given list (lets call it l1) is totally contained in a second list (l2)? for example: l1 = [1,2], l2 = [1,2,3,4,5] - l1 is contained in l2 l1 = [1,2,2,], l2 = [1,2,3,4,5] - l1 is not contained in l2 l1 = [1,2,3], l2 = [1,3,5,7] - l1 is not contained in l2 my problem is the second example, which makes it impossible to work with sets insteads of lists. But something like set.issubset for lists would be nice. greatz Johannes My best guess: from collections import Counter There's no reason to think that the Original Poster wants a multiset based solution. He asked about lists and sublists. That's a standard term, like substring: 12 is a substring of 01234. 21 and 13 are not. [1, 2] is a sublist of [0, 1, 2, 3, 4]. [2, 1] and [1, 3] are not. Since lists are ordered, so are sublists. That's reasonable; although except in the subject, the OP never uses the term 'sublist'; instead using more ambiguous terms like 'contains', 'is totally contained', etc., with definition by limited example. So it was a bit of a guess on my part of what was wanted. If the OP does want a solution that ignores order, then he needs to describe his problem better. As it turns out, in another response the OP says he wants [2,1,2] to be 'contained' by [1,2,2]. But in any case he always has sorted lists, in which case, interestingly, the multiset approach and your more canonical sublist approach yield the same results. Cheers - Chas -- http://mail.python.org/mailman/listinfo/python-list
Re: testing if a list contains a sublist
Check out collections.Counter if you have 2.7 or up. If you don't, google for multiset or bag types. On Mon, Aug 15, 2011 at 4:26 PM, Johannes dajo.m...@web.de wrote: hi list, what is the best way to check if a given list (lets call it l1) is totally contained in a second list (l2)? for example: l1 = [1,2], l2 = [1,2,3,4,5] - l1 is contained in l2 l1 = [1,2,2,], l2 = [1,2,3,4,5] - l1 is not contained in l2 l1 = [1,2,3], l2 = [1,3,5,7] - l1 is not contained in l2 my problem is the second example, which makes it impossible to work with sets insteads of lists. But something like set.issubset for lists would be nice. greatz Johannes -- http://mail.python.org/mailman/listinfo/python-list -- http://mail.python.org/mailman/listinfo/python-list
Re: testing if a list contains a sublist
In article mailman.27.1313450819.27778.python-l...@python.org, Johannes dajo.m...@web.de wrote: hi list, what is the best way to check if a given list (lets call it l1) is totally contained in a second list (l2)? for example: l1 = [1,2], l2 = [1,2,3,4,5] - l1 is contained in l2 l1 = [1,2,2,], l2 = [1,2,3,4,5] - l1 is not contained in l2 l1 = [1,2,3], l2 = [1,3,5,7] - l1 is not contained in l2 my problem is the second example, which makes it impossible to work with sets insteads of lists. But something like set.issubset for lists would be nice. greatz Johannes import re def sublist(l1, l2): s1 = ''.join(map(str, l1)) s2 = ''.join(map(str, l2)) return re.search(s1, s2) assert sublist([1,2], [1,2,3,4,5]) assert not sublist ([1,2,2], [1,2,3,4,5]) assert not sublist([1,2,3], [1,3,5,7]) (running and ducking) -- http://mail.python.org/mailman/listinfo/python-list
Re: testing if a list contains a sublist
On Tue, 16 Aug 2011 09:26 am Johannes wrote: hi list, what is the best way to check if a given list (lets call it l1) is totally contained in a second list (l2)? This is not the most efficient algorithm, but for short lists it should be plenty fast enough: def contains(alist, sublist): if len(sublist) == 0 or len(sublist) len(alist): return False start = 0 while True: try: p = alist.index(sublist[0], start) except ValueError: return False for i,x in enumerate(sublist): if alist[p+i] != x: start = p+1 break else: # for loop exits without break return True -- Steven -- http://mail.python.org/mailman/listinfo/python-list
