0

私は次の構造を持っています：

Node
{
    List<String> rootData;
    List<Node> Children;
}

およびコレクションとして

List<Node> lstOfTrees

最初の Structure は rootData にいくつかの単語を保持し (ノードのリストはここではあまり重要ではありません)、コレクションlstOfTreesにはツリーが含まれています。

問題は次のとおりです。 lstOfTreesには、複数のツリーがあります。一部のツリーには、他のツリーの rootData のサブセットがあります (必ずしもそうとは限りません)。lstOfTrees に他の rootData(s) のスーパーセットを持つツリーを保持したい (サブセットは無視する必要があります)。

例: lstOfTrees に次のようなツリーが含まれているとします。

1: {rootData: A, B, C, D}
2: {rootData: E, F, G}
3: {rootData: G, H}
4: {rootData: J, A, C}
5: {rootData: D, Z}

私が必要とする最終的な答えは、次を含む新しいリストにある必要があります。

1: {rootData: A, B, C, D}
2: {rootData: E, F, G}

これは、LINQ と TPL (またはより効率的な方法) を使用して実行できますか? 私はそれが効率的かつ正確であることを望んでいます。

編集：

次のコードはすべての場合に正しく機能するはずですか、それとも何か不足していますか??

lstOfTrees.Add(new node());
lstOfTrees[0].rootData = new List<string> {"A", "B", "C", "D"};
lstOfTrees.Add(new node());
lstOfTrees[1].rootData = new List<string> {"E", "F", "G"};
lstOfTrees.Add(new node());
lstOfTrees[2].rootData = new List<string> {"G", "H"};
lstOfTrees.Add(new node());
lstOfTrees[3].rootData = new List<string> {"J", "A", "C"};
lstOfTrees.Add(new node());
lstOfTrees[4].rootData = new List<string> {"D", "Z"};


Dictionary<int,node> dictOfTrees_indexToNode = Enumerable.Range(0, lstOfTrees.Count).ToDictionary(x=>x,x => lstOfTrees[x]);

List<int> notToInclude = new List<int>();
for (int i = 0; i < lstOfTrees.Count; i++)
{
    for (int j = 0; j < lstOfTrees.Count; j++)
    {
        if (j != i)
        {
            if (!lstOfTrees[j].Equals(lstOfTrees[i]))
            {
                if (lstOfTrees[j].rootData.Join(lstOfTrees[i].rootData, root => root, innerRoot => innerRoot,
                                                (root, innerRoot) => 1).Any())
                {
                    bool test = (lstOfTrees[j].rootData.Count > lstOfTrees[i].rootData.Count);
                    notToInclude.Add(test ? i : j);
                }
            }
        }
    }
}

List<node> finalList = new List<node>();
finalList.AddRange(lstOfTrees.Except(notToInclude.Select(s=>dictOfTrees_indexToNode[s])));

また、これから改善できますか？

4

1 に答える 1

1

文字列のリストのリストを検索するだけにテストするために、ケースを少し単純化しました。これは、小さな中間ステップの後に行っていることと同じである必要があります。

var list = lstOfTrees.Select(x => new HashSet<string>(x.rootData)).ToList();

また、ここでセットを使用する方が良い可能性は十分にあります。少なくとも、サンプル データに重複は見られません。これが 2 番目の変更です。

ここでセットを使用することは非常に重要です。そのため、実際にリスト内でデータを複製できる場合は、ソリューション全体を変更する必要があります。

結果は次のとおりです。

var list = new List<List<string>> {
        new List<string> {"A", "B", "C", "D"},
        new List<string> {"E", "F", "G"},
        new List<string> {"G", "H"},
        new List<string> {"J", "A", "C"},
        new List<string> {"D", "Z"}};

var sets = list.Select(x => new HashSet<string>(x)).ToList();

var result = sets.Select(x => sets.Where(y => x.Overlaps(y)) // You are looking not for 'subsets', but overlapping sets
                                  .OrderByDescending(y => y.Count)
                                  .FirstOrDefault())
                 .Distinct();

これは以下を返しますIEnumerable<HashSet<string>>:

{"A", "B", "C", "D"}, {"E", "F", "G"}

LINQPadでテスト済み:)

于 2013-10-02T08:47:41.093 に答える