0

我有以下结构：

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

和一个集合

List<Node> lstOfTrees

第一个结构包含一些关于 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();

此外，在这里使用集合可能会更好，至少我在示例数据中没有看到任何重复项，这是第二个更改。

在这里使用集合非常重要，所以如果数据实际上可以在列表中复制，那么整个解决方案就必须改变。

结果如下：

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 回答