时间戳

首页 > 解决方案 > 列表列表的组合，使每个组合都有唯一的元素

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

问题描述

好的，我有一个列表列表，就像标题所说的那样，我想组合 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 出现在第二个和第三个列表中。

我已经有一个执行此操作的代码，但它只是查找所有可能的组合并在将其添加到最终结果列表之前检查它们是否有效。由于当 K 变大时，这个列表非常大（153 个列表），所以花费的时间也非常大（在 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);
    }
}

标签： c#listcombinations

解决方案

如果我正确理解了您的问题，那么这将起作用：

 /// <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 来查找集合。

推荐阅读