一个列表的组合，使得每个组合都具有唯一的元素。

Question

我是一个有用的助手，可以翻译文本。

英译中：

好的，我有一个列表的列表，就像标题所说的一样，我想要制作k个列表的组合，在其中每个列表都具有与其余列表不同的元素。

例如：

我有以下列表：

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

这些列表的有效三个元素组合可能是：

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

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

无效的组合将会是：

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

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

我已经有一个代码可以做到这一点，但它只是找到所有可能的组合，然后检查它们是否有效，然后将其添加到最终结果列表中。由于列表列表相当大（153个列表），当K变大时，所需的时间也非常长（在K = 5时，需要大约10分钟）。

我想看看是否有一种有效的方法来做到这一点。 下面是我的当前代码（我要组合的列表是类项的属性）：

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);
    }
}

- Marcos R.

---

我不明白这个问题... 是的，我能看出什么是有效的，什么是无效的，但你想要做什么呢？过滤还是验证？ - TheGeneral

我想筛选出所有有效的组合并将它们添加到最终列表中。 - Marcos R.

你关心哪些内部列表将被删除吗？ - TheGeneral

我的意思是为什么你保留了{1,11}而不是{1,2,3}，我真的很困惑。你需要添加更多信息。 - TheGeneral

@TheGeneral 他想展示一个无效的例子与一个有效的例子相对应。这只是他想要在列表中收集并在最后输出给用户的众多可能性之一。确实是一个有趣的问题。 - Stavm

啊，是的，我现在明白了。 - TheGeneral

Answer 1

使用HashSethttps://msdn.microsoft.com/zh-cn/library/bb359438(v=vs.110).aspx来跟踪输入列表中的候选元素，以便构建输出的不同元素集合。

通过迭代元组输入列表并按以下方式评估每个元组作为候选项，累积一个非重叠元组的输出列表： 对于每个输入元组，将每个元组元素插入HashSet。如果您要插入的元素已经在集合中，则该元组不符合约束条件，应该跳过，否则元组元素与输出中已有的元素都是不同的。

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

- chrisg

Answer 2

如果我正确理解了你的代码，那么你正在将每个list<int>从输入传递给recursiveComb()函数。它看起来像这样：

for(int i = 0; i < inputnestedList.Count; i++)
{
    recursiveComb();
   // Inside of recursiveComb() you are using one more for loop with recursion.
   // This I observed from your first parameter i.e. List<int>
}

如果我错了，请纠正我

这导致时间复杂度大于O(n^2)

---

这是我的最简单的解决方案，使用两个for循环而无需递归。

List<List<int>> x = new List<List<int>>{ new List<int>(){1,2,3} , new List<int>(){1,11} , new List<int>(){2,3,6} , new List<int>(){6,5,7} , new List<int>(){4,8,9} };
List<List<int>> result = new List<List<int>>();
var watch = Stopwatch.StartNew();

for (int i = 0; i < x.Count;i++)
{
    int temp = 0;
    for (int j = 0; j < x.Count; j++)
    {
        if (i != j && x[i].Intersect(x[j]).Any())
            temp++;
    }

    // This condition decides, that elements of  ith list are available in other lists
    if (temp <= 1)
        result.Add(x[i]);
}
watch.Stop();
var elapsedMs = watch.Elapsed.TotalMilliseconds;

Console.WriteLine(elapsedMs);

现在当我打印执行时间时，输出为：

Execution Time: 11.4628

检查您的代码执行时间。如果您的代码执行时间大于我的，则可以认为它是高效的代码。

代码证明：DotNetFiddler

愉快的编码！

- Prasad Telkikar

---

你好，感谢你的回答。问题是我想生成多个大小为k的组合，并将它们添加到一个组合列表中。我想考虑所有可能的和有效的组合，并将它们添加到组合列表中。所以例如在我的原始帖子中，输出应该是一个包含所有有效组合的列表，就像我给出的那个一样。 - Marcos R.

你检查了我在dotnet fiddler上的实现了吗？这里是链接 https://dotnetfiddle.net/7SJhGQ。这个解决方案返回了你期望的输出。 - Prasad Telkikar

是的，我做了，问题是：那只是可能的一个组合，我想获取所有组合。 - Marcos R.

Answer 3

如果我正确理解了您的问题，那么这个方法可以解决：

 /// <summary>
        /// Get Unique List sets
        /// </summary>
        /// <param name="sets"></param>
        /// <returns></returns>
        public List<List<T>> GetUniqueSets<T>(List<List<T>> sets )
        {
            List<List<T>> cache = new List<List<T>>();

            for (int i = 0; i < sets.Count; i++)
            {
                // add to cache if it's empty
                if (cache.Count == 0)
                {
                    cache.Add(sets[i]);
                    continue;
                }
                else
                {
                    //check whether current item is in the cache and also whether current item intersects with any of the items in cache
                    var cacheItems = from item in cache where (item != sets[i] && item.Intersect(sets[i]).Count() == 0) select item;

                    //if not add to cache
                    if (cacheItems.Count() == cache.Count)
                    {
                        cache.Add(sets[i]);
                    }

                }
            }


            return cache;

        }

已测试，速度很快，查找集合只花费了00:00:00.0186033。

- Dharani Kumar