在树列表中标识根数据的子集
本文关键字:数据 子集 标识 列表 | 更新日期: 2023-09-27 18:33:29
我有以下结构:
Node
{
List<String> rootData;
List<Node> Children;
}
和集合作为
List<Node> lstOfTrees
第一个结构包含rootData上的一些单词(节点列表在这里并不重要),集合lstOfTrees包含树。
问题是:在 lstOfTrees 中,有多个树。一些树具有其他树的根数据的子集(可能,不一定)。我想让树在 lstOfTrees 中具有其他根数据的超集(子集应该被忽略)。
例:假设 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])));
另外,我可以从中改进吗?
我已经简化了一点情况,以便测试只是搜索字符串列表,这应该与您在中间小步骤后所做的相同:
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 :) 中测试