コレクション内のセットがコレクション内の別のセットのサブセットではないようなセットのコレクションを表す抽象的なデータ構造を探しています。
これは、挿入時に次の条件が満たされることを意味します。
A. すでに別の要素のサブセットである要素を挿入すると、元のコレクションが返されます。
B. 他の要素のスーパーセットである要素を挿入すると、スーパーセットが追加され、サブセットが削除されたコレクションが作成されます。
セットの要素の順序付けを想定すると、プレフィックス ツリーを使用してコレクションを表すことができます。これにより、条件 A を非常に迅速に処理できます (つまり、サブセットを挿入するよりも条件をチェックするのに時間がかかりません) が、条件 B を満たすには時間がかかります。
Bもすぐに会えるようなデータ構造があればいいなと思っています。
簡単なアプローチは、セットのリストを保持し、すべての着信セットに対して線形検索を実行することです（着信がサブセットであるかどうかをテストします）。
これは明らかに、線形探索の場合はO（n）時間で実行され、着信セットのサイズの場合はO（m）サイズで実行される可能性があります。したがって、O（n * m）の合計時間（セットの数と各セットのサイズ）。
もちろん、最も明白な最適化は、設定されたサイズにインデックスを付けることです。次に、同じかそれ以上のサイズのセットに対してのみ、各着信セットをテストします。（セットを小さなセットのサブセットにすることはできません、当たり前です！）。
頭に浮かぶ次の最適化は、要素のインデックスで作成することです。したがって、着信セットごとに、各要素を含む各セットの共通部分が見つかります。言い換えると、着信セット{a、b、c}の場合、要素{a}がセットA、B、およびDに存在し、要素{b}がB、E、およびFに存在し、{c}が存在することがわかります。 A、B、およびZに存在します...その場合、着信セットはBのサブセットです（{A、B、D}、{B、E、F}、および{A、B、Z}の共通部分）。
だから、それは私にはO（m * log（n））の複雑さのように聞こえます。（各着信セットの各要素に対してハッシュ検索を実行する必要があります）。挿入も同じ順序で行う必要があります（新しいセットのIDを各要素のマップに挿入します）。（Big-O分析では、もちろん2 * O（m log（n））はO（m log（n））に減少します）。
なんて馬鹿げたサイトでしょう。登録しましたので、やがて昨日からコメントできるかもしれません。それまでは、しかし...
@Stephen C：私の英語は十分だと思いますが、説明者を獲得したようです。しかし、彼は少し逃してしまいました。彼のコメントは次のようになります。
@Stephen C：任意の数の因子を見つけることは、確かにNP完全ですが、ここでは関係ありません。問題は、2つの数値のうち小さい方が、大きい方の単純な剰余演算を正確に除算するかどうかです。たとえば、p（bc）= 15はp（abcd）= 210の約数であるため、bcはabcdのサブセットです（abdとabcのセットも同様です）。
N個のセットの既存のコレクションに新しいセットSを追加するのはO（N）であり、Nに関係なく、多数の数の比較と除算にほぼ同じ時間がかかると想定しています。
セットのコレクション内の既存のエントリEごとに、p（S）<p（E）であり、p（S）がp（E）を正確に除算する場合は停止します。p（S）= p（E）の場合、停止します。p（S）> p（E）であり、p（E）がp（S）を正確に除算する場合は、Eを削除します。コレクションの最後に到達した場合は、Sを追加します。BigNumの配列は機能します。
@JL：私のオンサイトストーカーになりたい場合は、1）付加価値2）正確に努力してください。
セットA、B、...の個々のメンバーが別個の（そして比較的）素数にマップされ、各セットと一緒に、すべてのメンバーの積をp（A）、p（B）などとして格納する場合。サブセットとスーパーセットは、p（X）がp（Y）の因数であるか、またはその逆であるかによって見つけることができます。
非常に大きな数になる可能性がありますが、理論的には機能します。
例えば：
[abcd]-> [2 3 5 7]の場合、p（abc）= 30、p（abd）= 42、p（bc）= 15、p（abcd）= 210