Geek Answers Handbook

Ordered Subsets

I want to check if an ordered set is a subset of a larger 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

It works, but slowly when I test large tuples.

+4
source share
6 answers

You can simply use an iterator to track 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
+9
source

Easy way to do it

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

Use itertools for more efficiency itertools

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

It should start.

 >>> 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 list comprehension raises a KeyError , then obviously the answer is also False

+1
source

It should be pretty fast, but I have a faster one, I hope it will be 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 is faster than 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
+1
source

It uses a linear time approach (in the longest set), which does not require any hashing. It exploits the fact that since both sets are ordered, earlier elements in the set do not 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 am sure this is correct - let me know if you see any problems.

+1
source

How 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 to see if the subset of b is. You need it?

EDIT:

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

This does not apply to:

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

In this case, the order of a does not matter.

0
source

More articles:


All Articles