すべての入力セットにラベルを付けるとします。
A={1, 2, 3}, B={1, 2}, C={2, 3}, D={2, 4}, E={}
ここで、ユニバース内の要素ごとに 1 つの中間セットを作成し、それが表示されるセットのラベルを含めます。
1={A,B}
2={A,B,C,D}
3={A,C}
4={D}
次に、入力セットごとに、その要素のすべてのラベル セットの交点を計算します。
For A, {A,B} intesect {A,B,C,D} intersect {A,C} = {A} (*)
交差にセット自体以外のラベルが含まれている場合、それはそのセットのサブセットです。ここには他の要素がないので、答えはノーです。しかし、
For C, {A,B,C,D} intersect {A,C} = {A,C}, which means that it's a subset of A.
このメソッドのコストは、セットの実装によって異なります。ビットマップを考えてみましょう（あなたが示唆したように）。最大サイズ m および |U| の入力セットが n 個あるとします。宇宙のアイテム。次に、中間集合の構築により |U| が生成されます。サイズ n ビットのセットなので、それらを初期化するのに O(|U|n) 時間かかります。ビットの設定には O(nm) 時間が必要です。上記のように各交点を計算する(*)には O(mn) が必要です。すべての O(mn^2)。
これらをすべてまとめると、O(|U|n) + O(nm) +O(mn^2) = O(|U|n + mn^2) となります。同じ規則を使用すると、「すべてのペア」アルゴリズムは O(|U|^2 n^2) になります。m <= |U| なので、このアルゴリズムは漸近的に高速になります。定数係数を追加するための精巧な簿記がないため、実際にはより高速になる可能性があります。
追記：オンライン版
OP は、このアルゴリズムのオンライン バージョンがあるかどうかを尋ねました。つまり、入力セットが 1 つずつ到着するにつれて、最大セットのセットを段階的に維持できるものです。答えはイエスのようです。中間セットは、新しいセットが既に見たセットのサブセットであるかどうかをすぐに教えてくれます。しかし、それがスーパーセットかどうかをすばやく判断するにはどうすればよいでしょうか? もしそうなら、既存の極大集合はどれか? この場合、これらの極大集合はもはや極大ではなく、新しい集合に置き換えなければなりません。
重要なのは、 iffAのスーパーセットが のサブセットであることに注意することです(目盛りはセットの補数を示します)。BA'B'
このインスピレーションに従って、中間セットを以前と同じように維持します。新しい入力セットSが到着したら、上記と同じテストを行います:I(e)を入力要素の中間セットとしますe。それから、このテストは
For X = \intersect_{e \in S} . I(e), |X| > 0
S(この場合、はまだ に含まれていないため、上記の 1 ではなく 0 より大きいですI。) テストが成功した場合、新しいセットは既存の最大セットの (不適切な可能性がある) サブセットであるため、破棄できます。
それ以外の場合は、新しい最大セットとして追加する必要がありSますが、これを行う前に次の計算を行います。
Y = \intersect_{e \in S'} . I'(e) = ( \union_{e \in S'} . I(e) )'
ここでも目盛りは補数に設定されます。ユニオン形式は計算が少し速いかもしれません。Yによって置き換えられた最大セットが含まれSます。これらは最大コレクションと から削除する必要がありますI。最後にS最大セットとして追加し、の要素で更新Iします。S
例を見てみましょう。届いたらA追加していただきIます
1={A} 2={A} 3={A}
Bたどり着いたら、 を見つけX = {A} intersect {A} = {A}たので、捨てBて続けます。同じことが起こりCます。D到着すると が見つかるのでX = {A} intersect {} = {}、 に進みY = I'(1) intersect I'(3) = {} intersect {}ます。これは、最大集合Aが に含まれていないことを正しく示しているDため、削除するものはありません。Iしかし、それは新しい極大集合として追加されなければならず、
1={A} 2={A,D} 3={A} 4={D}
の到着はE変化を引き起こしません。新しいセットの到着を確認してF={2, 3, 4, 5}ください。我々は気づく
X = {A} isect {A,D} isect {A} isect {D} isect {}
だから捨てられないF。続ける
Y = \intersect_{e in {1}} I'(e) = I'(1) = {D}
これDは、 が のサブセットであることを示しているため、が追加されてFいる間は破棄する必要があります。F
1={A} 2={A,F} 3={A,F} 4={F} 5={F}
補数の計算は、アルゴリズムがオンラインであるため、トリッキーであると同時に便利です。入力補数のユニバースには、これまでに見た入力要素のみを含める必要があります。中間セットのユニバースは、現在の最大コレクション内のセットのタグのみで構成されます。多くの入力ストリームでは、このセットのサイズは安定するか、時間とともに減少します。
これがお役に立てば幸いです。
概要
ここで働く一般原則は、アルゴリズム設計でしばしば切り抜かれる強力なアイデアです。逆マップです。特定の属性を持つアイテムを見つけるために線形検索を行っていることに気付いたときはいつでも、属性からアイテムへのマップを作成することを検討してください。多くの場合、このマップの作成は安価であり、検索時間が大幅に短縮されます。代表的な例は、配列が置換された後に 'th 要素が占めるp[i]位置を示す置換マップです。i特定の場所に到達するアイテムを検索する必要がある場合は、線形時間操作であるaを検索する必要があります。一方、計算にそれほど時間がかからないような逆写像(そのため、そのコストは「隠されている」) ですが、papipi[p[i]] == ippi[a]一定の時間で目的の結果を生成します。
投稿者による実施
import collections
import operator
from functools import reduce # only in Python 3
def is_power_of_two(n):
"""Returns True iff n is a power of two. Assumes n > 0."""
return (n & (n - 1)) == 0
def eliminate_subsets(sequence_of_sets):
"""Return a list of the elements of `sequence_of_sets`, removing all
elements that are subsets of other elements. Assumes that each
element is a set or frozenset and that no element is repeated."""
# The code below does not handle the case of a sequence containing
# only the empty set, so let's just handle all easy cases now.
if len(sequence_of_sets) <= 1:
return list(sequence_of_sets)
# We need an indexable sequence so that we can use a bitmap to
# represent each set.
if not isinstance(sequence_of_sets, collections.Sequence):
sequence_of_sets = list(sequence_of_sets)
# For each element, construct the list of all sets containing that
# element.
sets_containing_element = {}
for i, s in enumerate(sequence_of_sets):
for element in s:
try:
sets_containing_element[element] |= 1 << i
except KeyError:
sets_containing_element[element] = 1 << i
# For each set, if the intersection of all of the lists in which it is
# contained has length != 1, this set can be eliminated.
out = [s for s in sequence_of_sets
if s and is_power_of_two(reduce(
operator.and_, (sets_containing_element[x] for x in s)))]
return out