Skip to content Skip to sidebar Skip to footer

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: def subset_test(a, b): return a in itertools.combinations(b, len

Solution 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

Solution 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

Solution 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


Solution 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.


Solution 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

Post a Comment for "Ordered Subsets Test"