As the title mentions,is there any builtins to do this job?I looked for that in dir(list) but got no usable one.Thanks.
views:
111answers:
3
+8
A:
Depends on what you mean by "contained". Maybe this:
if set(a) <= set(b):
print "a is in b"
nosklo
2010-04-06 05:54:32
Simple and Work.I'll check the usage of ` set `.Thanks.
SpawnCxy
2010-04-06 06:04:56
Seems functionally equivalent to my solution -- anybody know if either one has a performance advantage?
Etaoin
2010-04-06 06:06:47
Not sure I buy that -- the call to `sub` is linear, but the `<=` can't be free. Am I missing something?
Etaoin
2010-04-06 06:41:29
@Etaoin: `set` s are hashtables. Therefore the cost to access an object in a `set` is `O(1)`. In this code you have to go through all elements in `set(a)` (`O(len(set(a))`) and check whether this element is in `set(b)` (`O(1)`). But of course the overall cost us not (`O(len(sublist))`) as the sets have to build from the list first. I am not exactly sure what this costs but I think it should be `O(len(list))` so the overall cost is `O(len(a)) + O(len(b)) + O(len(set(a))`
Felix Kling
2010-04-06 06:49:56
Nice! Thanks -- I was missing the constant-time access to sets. +1 to your comment and this answer.(Also, of course, in my last comment, `sub` was a brainfart for `set`.)
Etaoin
2010-04-06 07:06:41
what if `a = [1,1,2,3]` and `b=[1,2,3]` ? `a` is not contained in `b` but your code says so.
Adrien Plisson
2010-04-06 10:17:26
@Adrien Plisson: That's why I said *Depends on what you mean by "contained"*.
nosklo
2010-04-06 11:03:49
+2
A:
Assuming that you want to see if all elements of sublist are also elements of superlist:
all(x in superlist for x in sublist)
Etaoin
2010-04-06 05:54:47
+1
A:
the solution depends on what values you expect from your lists.
if there is the possiblity of a repetition of a value, and you need to check that there is enough values in the tested container, then here is a time-inefficient solution:
def contained(candidate, container):
temp = container[:]
try:
for v in candidate:
temp.remove(v)
return True
except ValueError:
return False
test this function with:
>>> a = [1,1,2,3]
>>> b = [1,2,3,4,5]
>>> contained(a,b)
False
>>> a = [1,2,3]
>>> contained(a,b)
True
>>> a = [1,1,2,4,4]
>>> b = [1,1,2,2,2,3,4,4,5]
>>> contained(a,b)
True
of course this solution can be greatly improved: list.remove() is potentially time consuming and can be avoided using clever sorting and indexing. but i don't see how to avoid a loop here...
(anyway, any other solution will be implemented using sets or list-comprehensions, which are using loops internally...)
Adrien Plisson
2010-04-06 10:34:00