2

私が次のものを持っているとしましょう：

john: [a, b, c, d]
bob:  [a, c, d, e]
mary: [a, b, e, f]

または、グループを簡単に確認できるように、わずかに再フォーマットします。

john: [a, b, c, d]
bob:  [a,    c, d, e]
mary: [a, b,       e, f]

次のグループ化を生成するための最も一般的または最も効率的なアルゴリズムは何ですか?

[john, bob, mary]: [a]
[john, mary]:      [b]
[john, bob]:       [c,d]
[bob, mary]:       [e]
[mary]:            [f]
[john]:            []
[bob]:             []

すぐにグーグルで調べたところ、上記のキーは「パワーセット」を表しているようです。だから私は次の実装を計画していました：

1) パワーセット {{j, b, m}, {j, m}, {j, b} {b, m}, {m}, {j}, {b}} を生成 // j = john, b = ボブ、m = メアリー

2) すべての文字のセットを生成: {a, b, c, d, e, f}

3) サブセットを反復し、各文字について、サブセットのすべての要素に文字が存在するかどうかを確認します

そう...

subset = {j, b, m}

letter = a
    j contains a? true
    b contains a? true
    m contains a? true
        * add a to subset {j, b, m}

letter = b
    j contains b? true
    b contains b? false, continue

letter = c
    j contains c? true
    b contains c? true
    m contains c? false, continue
.....

subset = {j, m}
.....

より良い解決策はありますか？

EDIT : 上記のアルゴリズムには欠陥があります。たとえば、{j, m} には "a" も含まれますが、これは望ましくありません。各反復で、この文字がこのセットにない要素に「含まれていない」かどうかも確認するように、単純に変更できると思います。したがって、この場合、次のことも確認します。

if b does not contain a
4

2 に答える 2

0

ステップ 3 (サブセットの繰り返し) は、パワー セットの各要素に対して「j が a を含む」または「j にない」のいずれかを行うため、非効率的です。

これが私が提案するものです：

1) べき集合 {{j, b, m}, {j, m}, {j, b} {b, m}, {m}, {j}, {b}} を生成します。最終出力で空のマッピングを気にしない場合、この手順は必要ありません。

2) 元のデータ構造のすべての要素を繰り返し処理し、次のように構成します。

[a] : [j, b, m]
[b] : [j, m]
[c] : [j, b]
[d] : [j, b]
[e] : [b, m]
[f] : [m]

3) 上記の構造を逆にして集計 ([j, b,...] のマップを [a,b...] のリストに使用) して、これを取得します。

[j, b, m] : [a]
[j, m] : [b]
[j, b] : [c, d]
[b, m] : [e]
[m] : [f]

4) 3 と 1 を比較して、残りの空のマッピングを埋めます。

編集: Hers は Java の完全なコードです 

    // The original data structure. mapping from "john" to [a, b, c..] 
    HashMap<String, HashSet<String>> originalMap = new HashMap<String, HashSet<String>>();

    // The final data structure. mapping from power set to [a, b...]
    HashMap<HashSet<String>, HashSet<String>> finalMap = new HashMap<HashSet<String>, HashSet<String>>();

    // Intermediate data structure. Used to hold [a] to [j,b...] mapping
    TreeMap<String, HashSet<String>> tmpMap = new TreeMap<String, HashSet<String>>();

    // Populate the original dataStructure
    originalMap.put("john", new HashSet<String>(Arrays.asList("a", "b", "c", "d")));
    originalMap.put("bob", new HashSet<String>(Arrays.asList("a", "c", "d", "e")));
    originalMap.put("mary", new HashSet<String>(Arrays.asList("a", "b", "e", "f")));

    // Hardcoding the powerset below. You can generate the power set using the algorithm used in googls guava library.
    // powerSet function in https://code.google.com/p/guava-libraries/source/browse/guava/src/com/google/common/collect/Sets.java
    // If you don't care about empty mappings in the finalMap, then you don't even have to create the powerset
    finalMap.put(new HashSet<String>(Arrays.asList("john", "bob", "mary")), new HashSet<String>());
    finalMap.put(new HashSet<String>(Arrays.asList("john", "bob")), new HashSet<String>());
    finalMap.put(new HashSet<String>(Arrays.asList("bob", "mary")), new HashSet<String>());
    finalMap.put(new HashSet<String>(Arrays.asList("john", "mary")), new HashSet<String>());
    finalMap.put(new HashSet<String>(Arrays.asList("john")), new HashSet<String>());
    finalMap.put(new HashSet<String>(Arrays.asList("bob")), new HashSet<String>());
    finalMap.put(new HashSet<String>(Arrays.asList("mary")), new HashSet<String>());

    // Iterate over the original map to prepare the tmpMap.
    for(Entry<String, HashSet<String>> entry : originalMap.entrySet()) {
        for(String value : entry.getValue()) {
            HashSet<String> set = tmpMap.get(value);
            if(set == null) {
                set = new HashSet<String>();
                tmpMap.put(value, set);
            }
            set.add(entry.getKey());
        }
    }

    // Iterate over the tmpMap result and add the values to finalMap
    for(Entry<String, HashSet<String>> entry : tmpMap.entrySet()) {
        finalMap.get(entry.getValue()).add(entry.getKey());
    }

    // Print the output
    for(Entry<HashSet<String>, HashSet<String>> entry : finalMap.entrySet()) {
        System.out.println(entry.getKey() +" : "+entry.getValue());
    }

上記のコードの出力は次のようになります。

[bob] : []
[john] : []
[bob, mary] : [e]
[bob, john] : [d, c]
[bob, john, mary] : [a]
[mary] : [f]
[john, mary] : [b]
于 2014-11-18T23:03:34.330 に答える