Ordered subsets test

I want to test if an ordered set is a subset of a bigger ordered set. I used tuples and itertools.combinations:

itertools.combinations

def subset_test(a, b):
return a in itertools.combinations(b, len(a))


For instance,

>>> subset_test((0, 1, 2), (0, 3, 1, 4, 2))
True
>>> subset_test((0, 1, 2), (0, 3, 2, 4, 1))
False


It works, but is slow when I test big tuples.

list

6 Answers
6

You can simply use an iterator to keep track of the position in B

>>> A = (0, 1, 2)
>>> B = (0, 3, 1, 4, 2)
>>> b_iter = iter(B)
>>> all(a in b_iter for a in A)
True


in

in

in

__contains__

dict

in

Simple way of doing this

>>> a = (0, 1, 2)
>>> b = (0, 3, 1, 4, 2)
>>> filter(set(a).__contains__, b) == a
True


For greater efficiency use itertools

itertools

>>> from itertools import ifilter, imap
>>> from operator import eq
>>> all(imap(eq, ifilter(set(a).__contains__, b), a))
True


filter(functools.partial(operator.contains, a), b)

This should get you started

>>> A = (0, 1, 2)
>>> B = (0, 3, 1, 4, 2)
>>> b_idxs = v:k for k,v in enumerate(B)
>>> idxs = [b_idxs[i] for i in A]
>>> idxs == sorted(idxs)
True


If the list comprehension throws a KeyError, then obviously the answer is also False

KeyError

False

Here's a linear time approach (in the longest set) that doesn't require any hashing. It takes advantage of the fact that, since both sets are ordered, earlier items in the set don't need to be re-checked:

>>> def subset_test(a, b):
... b = iter(b)
... try:
... for i in a:
... j = b.next()
... while j != i:
... j = b.next()
... except StopIteration:
... return False
... return True
...


A few tests:

>>> subset_test((0, 1, 2), (0, 3, 1, 4, 2))
True
>>> subset_test((0, 2, 1), (0, 3, 1, 4, 2))
False
>>> subset_test((0, 1, 5), (0, 3, 1, 4, 2))
False
>>> subset_test((0, 1, 4), (0, 3, 1, 4, 2))
True


I'm pretty sure this is right -- let me know if you see any problems.

This should be pretty quick, but I have a faster one in mind I hope to have down soon:

def is_sorted_subset(A, B):
try:
subset = [B.index(a) for a in A]
return subset == sorted(subset)
except ValueError:
return False


Update: here's the faster one I promised.

def is_sorted_subset(A, B):
max_idx = -1
try:
for val in A:
idx = B[max_idx + 1:].index(val)
if max(idx, max_idx) == max_idx:
return False
max_idx = idx
except ValueError:
return False
return True


B

list.index

What about this?

>>> a = (0, 1, 2)
>>> b = (0, 3, 1, 4, 2)
>>> set(a).issubset(set(b))
True


In this example a and b have ordered and unique elements and it checks if a is subset of b. Is this you want?

EDIT:

According to @Marcos da Silva Sampaio: "I want to test if A is a subset of the ordered set B."

It wouldn't be the case of:

>>> a = (2, 0, 1)
>>> b = (0, 3, 1, 4, 2)
>>> set(b).issuperset(a)
True


In this case the order of a doesn't matters.

a

(2, 1, 0)

(0, 3, 1, 4, 2)

Thanks for contributing an answer to Stack Overflow!

But avoid …

To learn more, see our tips on writing great answers.

Required, but never shown

Required, but never shown

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.