5

特定のセットのサブセットであるセットの有限コレクション内のセットを見つけるための最良のアルゴリズムは何ですか?

たとえば、

A = {1, 2}
B = {2, 3, 4}
C = {3, 5}
D = {6}

および X ={1, 2, 3, 5}

このとき、A と C は X の部分集合です。

線形時間の複雑さでこれを行うことができるアルゴリズムはありますか?

実装に関する注意:セットのメンバーは一般に非常に限られた範囲のものです。そのため、C++ ビットセットを使用してアルゴリズムを実装することをお勧めします。できませんでしたか？

編集:コレクション内のセットの数は、通常、X 内の要素の数 (例) よりも非常に大きくなります。Xの要素数に関してこれを線形にする方法はありますか? おそらくハッシュか何かを使用していますか？

4

2 に答える 2

7

ちょっとの間、64 の可能な要素を想定してみましょう。

次に、各要素をビットとして表す場合、64 ビット長の整数を使用して各セットを表すことができa & bます。 If (および if only)がthenのサブセットです。ab
aba & b == a

もちろん、64 ビット以上が必要な場合はビットセットを使用できます。

要素の範囲が広い場合は、ハッシュ テーブルを使用してスーパーセットを (1 回) 格納し、潜在的なサブセットを反復して、すべての要素が含まれているかどうかを確認します。
入力サイズに線形です (平均的なケース)。

編集: (編集された質問への応答)

O(|X| + n*min{m,|X|})データに関するいくつかの情報を事前に保存していない限り、 |X|よりも前に実行することはできません。はセット X のサイズ、 はセットnの数、 はセットmの平均サイズです。
この理由は、最悪の場合、すべてのセットのすべての要素を読み取る必要があるためです (各セットについて最後に読み取った要素によって、それがサブセットであるかどうかが決まるため)。セット。

推奨される解決策は次の とおりです。
ビットセット:O(|X|*n)
ハッシュ ソリューション: O(|X| + min{m,|X|}*n)(平均的なケース)

ハッシュ ソリューションはより良い漸近的複雑さを提供しますが、定数はビットセットに対してはるかに優れているため、ビットセット ソリューションはおそらく小さい|X|

于 2012-09-24T06:32:54.917 に答える
1

いくつかの余分な構造を構築する時間が制限されていない場合、 O(log(n)) ソリューションは、個々のセットを表すビットシーケンスをTrieに格納することです。

Amit が想定しているように、セット (別名ビット文字列) を他のすべてのセットと比較する必要はありません。並べ替えられたビット文字列のコレクションがある場合、比較ごとにバリアントの数が明らかに半分に減少します。はい、もちろん、ビットセット トライを構築する時間は O(n*log(n)) のようなものですが、それは前処理です。

于 2012-09-24T08:30:12.437 に答える