5

順序集合がより大きな順序集合のサブセットであるかどうかをテストしたいと思います。タプルを使用しました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

動作しますが、大きなタプルをテストすると遅くなります。

4

6 に答える 6

14

イテレータを使用して、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
于 2012-08-05T23:11:15.460 に答える
3

これを行う簡単な方法

>>> 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
于 2012-08-05T22:18:43.810 に答える
1

これはかなり速いはずですが、私はもっと速いものを念頭に置いています。

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
于 2012-08-05T22:41:04.397 に答える
1

これで始められるはずです

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

リスト内包表記がをスローする場合KeyError、明らかに答えはFalse

于 2012-08-05T22:22:21.323 に答える
1

これは、ハッシュを必要としない線形時間アプローチ（最長のセット）です。両方のセットが注文されているため、セット内の以前のアイテムを再チェックする必要がないという事実を利用しています。

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

これは正しいと確信しています。問題が発生した場合はお知らせください。

于 2012-08-05T22:51:43.413 に答える
-1

これはどうですか？

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

この例では、aとbに順序付けられた一意の要素があり、aがbのサブセットであるかどうかをチェックします。これはあなたが欲しいですか？

編集：

@Marcos da Silva Sampaioによると、「Aが順序集合Bのサブセットであるかどうかをテストしたい」とのことです。

次の場合には当てはまりません。

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

この場合、aの順序は重要ではありません。

于 2012-08-05T22:56:09.690 に答える