c# - 从列表列表中查找 2 个匹配的子列表

Question

在我的小 C# 爱好项目中遇到了这个我无法完全解决的小问题。我陷入了许多困惑而复杂的嵌套循环中。希望有人能给个启发。

我有一个 int 列表列表，即 List<List<int>> .假设每个 int 列表都包含唯一的项目。列表的最小大小为 5。我需要找到正好两个 int 列表(列表 A 和列表 B)共享正好三个 公共(public)项目和另一个 int 列表(列表 X)包含恰好一个这些常见项目。另一个条件必须成立:其他列表都不包含这三项中的任何一项。

例如:

List<List<int>> allLists = new List<List<int>>();
allLists.Add(new List<int>() {1, 2, 3, 4});
allLists.Add(new List<int>() {1, 2});
allLists.Add(new List<int>() {3, 4});
allLists.Add(new List<int>() {3, 4, 5, 6, 7, 8, 9});
allLists.Add(new List<int>() {4, 6, 8});
allLists.Add(new List<int>() {5, 7, 9, 11});
allLists.Add(new List<int>() {6, 7, 8});

对于上面的例子，我希望找到一个解决方案:

ListA and ListB: [3, 5] // indices of allLists
ListX: 6 // index of allLists
The three shared items: [5, 7, 9]
The matching item in ListX: 7

注意:根据列表的内容，可能有多种解法。也可能出现没有找到满足上述条件的列表的情况。

我陷入了一些困惑的嵌套循环。我在想是否有人可以想出一个简单有效的解决方案(可能使用 LINQ？)

最初我有如下愚蠢的事情:

for (var i = 0; i < allLists.Count - 1; i++)
{
    if (allLists[i].Count > 2)
    {
        for (var j = i + 1; j < allLists.Count; j++)
        {
            List<int> sharedItems = allLists[i].Intersect(allLists[j]).ToList();
            if (sharedItems.Count == 3)
            {
                foreach (var item in sharedItems)
                {
                    int itemCount = 0;
                    int? possibleListXIndex = null;
                    for (var k = 0; k < allLists.Count; k++)
                    {
                        if (k != i && k != j && allLists[k].Contains(item))
                        {
                            // nested loops getting very ugly here... also not sure what to do....
                        }
                    }
                }
            }
        }
    }
}

扩展问题

我的项目中有这个问题的扩展版本。它以相同的方式:

• 找到恰好三个 int 列表(列表 A、列表 B 和列表 C)，它们共享恰好四个共同项
• 找到另一个包含恰好上述常见项目的int列表(List X)
• 其他列表均不包含这四项。

我在想原始算法可能会变得可扩展以涵盖扩展版本，而无需从头开始编写另一个版本的算法。对于上面的嵌套循环，我想我别无选择，只能添加至少两个更深层次的循环来覆盖四个项目和三个列表。

我提前感谢大家的贡献!非常感谢。

Answer 1

这里有一个解决方案可以解决您的问题。我不会完全称其为高效，但遵循起来非常简单。

它将工作分两步进行。首先，它构建了一个初始候选人列表，其中他们恰好有三个匹配项。第二步添加 ListX 属性并检查是否满足其余条件。

var matches = allLists.Take(allLists.Count - 1)
    .SelectMany((x, xIdx) => allLists
        .Skip(xIdx + 1)
        .Select(y => new { ListA = x, ListB = y, Shared = x.Intersect(y) })
        .Where(y => y.Shared.Count() == 3))
    .SelectMany(x => allLists
        .Where(y => y != x.ListA && y != x.ListB)
        .Select(y => new 
        { 
             x.ListA, 
             x.ListB, 
             x.Shared, 
             ListX = y, 
             SingleShared = x.Shared.Intersect(y) 
        })
        .Where(y => y.SingleShared.Count() == 1 
            && !allLists.Any(z => z != y.ListA 
                && z != y.ListB 
                && z != y.ListX 
                && z.Intersect(y.Shared).Any())));

运行以下代码后，您将获得以下输出。

列表A。 3: [3, 4, 5, 6, 7, 8, 9] ListB. 5: [5, 7, 9, 11] => [5, 7, 9], ListX. 6:[6, 7, 10] => 7

matches.ToList().ForEach(x => {
    Console.WriteLine("ListA. {0}: [{1}] ListB. {2}: [{3}] => [{4}], ListX. {5}:[{6}] => {7}", 
        allLists.IndexOf(x.ListA), 
        string.Join(", ", x.ListA), 
        allLists.IndexOf(x.ListB), 
        string.Join(", ", x.ListB), 
        string.Join(", ", x.Shared),
        allLists.IndexOf(x.ListX),
        string.Join(", ", x.ListX), 
        string.Join(", ", x.SingleShared));