2

識別子のセットが添付された4つの異なる値A、B、C、Dがあるとします。

A = {1,2,3,4,5}
B = {8,9,4}
C = {3,4,5}
D = {12,8}

そして、識別子のセットS {1,30,3,4,5,12,8}が与えられた場合、CとDを返すようにします。つまり、Sがスーパーセットであるセットのグループからすべてのセットを取得します。

このタスクを効率的に実行するためのアルゴリズムはありますか（できればメモリの複雑さが低い場合。データを保存するために外部デバイスを使用することはできません）？簡単な解決策は、スーパーセットSの各メンバーに対して、そのメンバーを含むセットのリスト（基本的に転置インデックス）を取得し、返されたセットごとに、すべてのメンバーがスーパーセットにあることを確認することです。残念ながら、スーパーセットには平均して各セットに少なくとも1つのメンバーが含まれるため、このアプローチではパフォーマンスが大幅に低下し、許容できない結果になります。

私はこれをJavaで行おうとしています。セットは整数で構成され、それらが識別する値はオブジェクトです。セットのコレクションは静的ではなく、実行中に変更される可能性があります。ただし、セット数には多少の制限があります。セットサイズに制限はありません。しかし、平均して1から20の間です。

4

3 に答える 3

3
  1. Sの各要素xを調べます。
  2. x∈tである各セットtについて、 tに関連付けられたカウンター（ tカウントと呼びます）をインクリメントします。
  3. 結局のところ、t count =|である各セットtについて t |、あなたはt⊆Sであることを知っています。

応用。

ステップ2の後。

Aカウント=4、
Bカウント= 1、
Cカウント= 3、
Dカウント=2。

ステップ3の処理。

カウント≠| A | （4≠5）—拒否、
Bカウント≠| B | （1≠3）—拒否、
Cカウント= | C | （3 = 3）—受け入れる、
Dカウント= | D | （2 = 2）—受け入れます。

于 2009-12-26T10:03:11.103 に答える
1

cgkanchi の後の注記: 次のアルゴリズムは、実際にはセットではなく配列を使用することを前提としています。そうでない場合は、セットの交差を実装するメソッドを探す必要があります。そうすれば問題は簡単です。これは、配列を使用して交差の概念を実装する方法についてです。

  1. O(1) 空間のインプレース ソートにヒープソートを使用してすべてのセットをソートします。それは O(nlogn) で実行され、すぐに返済されます。

  2. すべてのセットの各セットについてL:

    2.1. j = 0

    2.2. のi要素の場合L:

    2.2.1. 他に拒否するj要素の検索から開始します。とと が十分に大きい場合は、バイナリ検索または補間検索を使用します (2 番目のものについては、データ分布を見てください)。L[i]SL[i] = S[j]LS

    2.3. 承認

于 2009-12-29T00:36:47.183 に答える
0

Java に関しては、 Sの要素のルックアップ テーブルにHashtableを使用します。次に、 Xの各要素について、それがSのサブセットであるかどうかをテストするセットであり、ルックアップ テーブルにあるかどうかをテストします。Xのすべての要素がSにもある場合、SはXのスーパーセットです。

于 2009-12-26T10:18:33.627 に答える