c# - 列表列表的组合，使每个组合都有唯一的元素

Question

好吧，我有一个列表列表，如标题所示，我想组合 k 个列表，其中每个列表都具有与其余列表不同的元素。

示例:

我有以下列表:

{ {1,2,3} , {1,11} , {2,3,6} , {6,5,7} , {4,8,9} }

这些列表的有效 3 大小组合可以是:

{ {1,11}, {4,8,9} ,{6,5,7} }

这只是其中一个有效组合，我要返回的是K个列表所有有效组合的列表。

无效的组合是:

{ {1,11} ,{2, 3, 6}, {6, 5, 7} } 

因为元素 6 出现在第二个和第三个列表中。

我已经有了执行此操作的代码，但它只是找到所有可能的组合并在将其添加到最终结果列表之前检查它们是否有效。由于这个列表列表非常大(153 个列表)，当 K 变大时，所花费的时间也大得离谱(在 K = 5 时，我大约需要 10 分钟。)

我想看看是否有一种有效的方法来做到这一点。下面是我当前的代码(我想合并的列表是 Item 类的属性):

public void recursiveComb(List<Item> arr, int len,  int startPosition, Item[] result)
{
    if (len == 0)
    {            
        if (valid(result.ToList()))
        {                
          //Here I add the result to final list

          //valid is just a function that checks if any list has repeated elements in other  
        }            
        return;
    }

    for (int i = startPosition; i <= arr.Count - len; i++)
    {       
        result[result.Length - len] = arr[i];
        recursiveComb(arr, len - 1,  i + 1, result);
    }
}

Answer 1

使用哈希集 https://msdn.microsoft.com/en-us/library/bb359438(v=vs.110).aspx在构建列表/元组输入列表中候选者的输出时跟踪不同的元素

通过遍历元组的输入列表来累积非重叠元组的输出列表，并将每个元组评估为候选者，如下所示:对于每个输入元组，将每个元组元素插入到 HashSet 中。如果您尝试插入的元素已经在集合中，则该元组未通过约束并且应该被跳过，否则元组元素与输出中已有的元素完全不同。

哈希集对象有效地维护了您接受的元组列表中不同项目的注册表。