python - Ordered subsets test

Question

I want to test if an ordered set is a subset of a bigger ordered set. I used tuples and 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.

Answer 1

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

Answer 2

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

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

Answer 3

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

Answer 4

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.

Answer 5

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

Answer 6

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.