列表列表的组合使每个组合具有唯一元素

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

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

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

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