2

大きな任意のセット S とセット S_n のリストが与えられた場合、S のサブセットである S_n 内のすべてのセットを見つけます。

つまり、PowerSet(S) と S_n の交点です。

この種の計算をすばやく行うための Java ライブラリはありますか? セット S_n のリストは比較的小さく、多くても数百であり、これらのセットには多くても 10 個のアイテムが含まれます。ただし、(実行時に決定される) 任意のセットには、(1000 個のセットのうち) 20 個もの項目が含まれる可能性があるため、膨大なパワー セットがあります。

おそらくある種のオフライン計算を行って、この決定をその場で非常に迅速に（50ミリ秒以下）行う方法を探しています。

例: S = { 1, 2, 3 }

S_n = [ { 1 }, { 1, 2 }, { 5, 4, 6 } ]

結果 = [ { 1 }, { 1, 2 } ]

4

4 に答える 4

1

疑似コード

for each subset s_n
    if (s.containsAll(s_n)) {
        add it to the result list
    }
于 2012-10-02T16:25:52.387 に答える
1

retainAll(Collection<?> c) インターフェイスで宣言されている標準メソッドを使用できると思いますjava.util.Set

于 2012-10-02T16:26:54.540 に答える
0

Google の Guava ライブラリを参照してください。

https://code.google.com/p/guava-libraries/wiki/CollectionUtilitiesExplained#Sets

これにより、コレクションに対する追加の操作だけでなく、パワーセットもカウントされ、優れたパフォーマンスが保証されます（パワーセットを計算していることを考慮して.....）。

于 2012-10-02T16:30:38.097 に答える
0

Guava Setsで試してみてください。

powerSet や Intersection など、必要なユーティリティが多数含まれています。

于 2012-10-02T16:31:06.490 に答える