1

ネストされたハッシュセット内でサブセットの複数の組み合わせを見つけなければならないという問題があります。基本的に、「マスター」のネストされたHashSetがあり、「可能な」ネストされたHashSetのコレクションから、「マスター」の同時サブセットである可能性のある「可能性」をプログラムで見つける必要があります。

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

            var master = new HashSet<HashSet<string>>(new HashSet<string>[] {
                        new HashSet<string>( new string[] { "A", "B", "C"}),
                        new HashSet<string>( new string[] { "D", "E"}),
                        new HashSet<string>( new string[] { "F"})
                    }
                ); 
            var possible1  = new HashSet<HashSet<string>>(new HashSet<string>[] {
                        new HashSet<string>( new string[] { "A", "B", "C"}),
                        new HashSet<string>( new string[] { "F"})
                    }
                 );
            var possible2 = new HashSet<HashSet<string>>(new HashSet<string>[] {
                        new HashSet<string>( new string[] { "D", "E"})
                    }
                 ); 
            var possible3 = new HashSet<HashSet<string>>(new HashSet<string>[] {
                        new HashSet<string>( new string[] { "F"})
                    }
                 ); 
            var possible4 = new HashSet<HashSet<string>>(new HashSet<string>[] {
                        new HashSet<string>( new string[] { "X", "Y", "Z"})
                    }
                ); 
            var possible5 = new HashSet<HashSet<string>>(new HashSet<string>[] {
                        new HashSet<string>( new string[] { "A", "B" }),
                        new HashSet<string>( new string[] { "D", "E"})
                    }
                );

アルゴリズムから取得する必要がある出力は次のようになります。

すべての可能な組み合わせサブセット:

possible1 and possible2
possible3 and possible5
possible2 and possible3
possible1
possible2
possible3
possible5

私はこれにアプローチする最善の方法を見つけようとしています。もちろん、力ずくのオプションもありますが、できればそれを避けようとしています。

私の質問が十分に明確であることを願っています。

編集

サブセットを構成するものをさらに詳しく説明するために、マスター {{"A","B","C"},{"C","D","E",F"},{ "X","Y","Z"}} :

  • {{"A","B"}{"C","D"}} は、
  • {{"A","B","C"},{"X","Y"}} はサブセットになります
  • {{"A","B"},{"A","B"}} はサブセットではありません
  • {{"A","B","C","D"}} はサブセットではありません
  • {{"A","B","C"},{"C","D","X"}} はサブセットではありません

基本的に、各子セットは、マスター内の対応する子のサブセットである必要があります。

4

2 に答える 2

1

ブルートフォースを使用する:

public static int IsCsInMaster(HashSet<string> childSubset, List<HashSet<string>> master, int startIndex)
{
    for (int i = startIndex; i < master.Count; i++)
        if (childSubset.IsSubsetOf(master[i])) return i;

    return -1;
}

public static bool IsChildInMaster(List<HashSet<string>> child, List<HashSet<string>> master)
{
    foreach (var childSubset in child) if (IsCsInMaster(childSubset, master, 0) == -1) return false;

    return true;
}

public static bool IsChildInMasterMulti(List<HashSet<string>> child, List<HashSet<string>> master)
{
    Dictionary<int, int> subsetChecker = new Dictionary<int, int>();
    List<IEnumerable<int>> multiMatches = new List<IEnumerable<int>>();
    int subsetIndex;

    // Check for matching subsets.
    for (int i = 0; i < child.Count; i++)
    {
        subsetIndex = 0;
        List<int> indexes = new List<int>();

        while ((subsetIndex = IsCsInMaster(child[i], master, subsetIndex)) != -1)
        {
            indexes.Add(subsetIndex++);
        }

        if (indexes.Count == 1)
        {
            subsetIndex = indexes[0];
            if (subsetChecker.ContainsKey(subsetIndex)) return false;
            else subsetChecker[subsetIndex] = subsetIndex;
        }
        else
        {
            multiMatches.Add(indexes);
        }
    }

    /*** Check for multi-matching subsets. ***/ //got lazy ;)
    var union = multiMatches.Aggregate((aggr, indexes) => aggr.Union(indexes));

    // Filter the union so only unmatched subset indexes remain.
    List<int> filteredUion = new List<int>();
    foreach (int index in union)
    {
        if (!subsetChecker.ContainsKey(index)) filteredUion.Add(index);
    }

    return (filteredUion.Count >= multiMatches.Count);
}

そしてコードで：

IsChildInMasterMulti(possible2, master)

{{"A","B"},{"A","B"}}ただし、コードはケースを処理しません。それはもっと難しいです（マスターで使用されているサブセットにフラグを立てる、おそらく個々の要素でさえも - 再帰的に）。

Edit2 : 3 番目のメソッドは、{{"A","B"},{"A","B"}}ケース (およびそれ以上) も処理します。

于 2010-07-06T19:48:45.643 に答える
0

可能な限り簡単なソリューションを使用してください。

他の誰かがあなたのコードを見なければならない場合、彼らはできるだけ少ない労力で何をしているのかを理解できるようにすべきだということを心に留めておいてください。あなたの説明からあなたが何をしたいのかを理解するのはすでに難しいと思いました.コードを読む必要はまだありません.

動作後に遅すぎることがわかった場合は、最適化してください。

可能であれば単体テストを書いてください。単体テストは、最適化されたソリューションも正しく機能していることを確認し、他の人が変更によって何も壊れていないことを確認するのに役立ちます。

于 2010-07-06T19:01:02.740 に答える