python - 有序子集测试

Question

我想测试一个有序集是否是一个更大的有序集的子集。我使用元组和itertools.combinations：

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

例如，

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

它可以工作，但是当我测试大元组时速度很慢。

Answer 1

您可以简单地使用迭代器来跟踪 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

这样做的简单方法

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

为了提高效率使用itertools

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

Answer 3

这应该让你开始

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

如果列表推导抛出 a KeyError，那么显然答案也是False

Answer 4

这应该很快，但我有一个更快的想法，我希望尽快完成：

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

更新：这是我承诺的更快的。

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 5

这是一种不需要任何散列的线性时间方法（在最长的集合中）。它利用了这样一个事实，因为两个集合都是有序的，所以不需要重新检查集合中较早的项目：

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

几个测试：

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

我很确定这是对的——如果您发现任何问题，请告诉我。

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.