c# - 如何使用条件过滤 int 列表列表？

Question

我有这个List<List<int>> :

{{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}} 

在这个列表中有6个列表，包含从1到4的数字，每个数字出现3次；

我想过滤它以获得:

{{1,2}{1,3}{2,4}{3,4}}

这里每个数的出现次数都是2；

列表是动态生成的，我希望能够根据出现情况进行动态过滤；

编辑-更多详细信息

我需要计算一个数字在 List<List<int>> 中出现了多少次，对于上面的示例是 3。然后我想从 List<List<int>> 中排除列表为了将次数从3次减少到2次，对我来说主要的问题是找到一种不阻塞我的计算机的方法 :)，并且让每个数字出现 2 次(强制性的)；

Answer 1

好吧，如果它总是 2 个数字的组合，并且它们必须在列表中出现 N 次，这意味着取决于 N 你将拥有:

4(不同数字)x 2(嘿必须出现的次数)= 8 数字 = 4 对

4 x 3(次)= 12 = 6(对)

4 x 4 = 16 = 8 对

这意味着 - 我们知道必须从 6 对中选择最符合条件的 4 对

所以基于基本组合学 ( https://www.khanacademy.org/math/probability/probability-and-combinatorics-topic/permutations/v/permutation-formula )我们有一个 6!/2! = (6*5*4*3*2*1)/(2*1)= 360种可能的排列

基本上，您可以通过 360 种不同的方式将第二个列表放在一起。

因为您如何排列列表中的项目(列表中项目的顺序)并不重要，所以可能的组合数是 6!/(2!*4!) = 15 https://www.khanacademy.org/math/probability/probability-and-combinatorics-topic/combinations-combinatorics/v/combination-formula

所以事情是 - 您的问题有 15 个可能的答案。这意味着 - 你只需要循环 15 次。从 6 项列表中选择 4 项只有 15 种方法

这似乎是您的“杀死机器”问题的解决方案。

所以下一个问题 - 我们如何找到所有可能的“组合”让我们定义我们可以从输入数组中选择的所有可能项目例如第 1、第 2、第 3 和第 4..

1,2,3,4....... 1,2,3,5...... 1,2,3,6 ...

所有的组合都是(从这里https://stackoverflow.com/a/10629938/444149)

static IEnumerable<IEnumerable<T>>  GetKCombs<T>(IEnumerable<T> list, int length) where T : IComparable
    {
        if (length == 1) return list.Select(t => new T[] { t });
        return GetKCombs(list, length - 1)
            .SelectMany(t => list.Where(o => o.CompareTo(t.Last()) > 0),
                (t1, t2) => t1.Concat(new T[] { t2 }));
    }

并调用 with (因为有 6 个项目可供选择，索引为 0、1、2、3、4 和 5)

 var possiblePicks = GetKCombs(new List<int> { 0, 1, 2, 3, 4, 5 }, 4);

我们得到 15 种可能的组合所以现在 - 我们尝试从第一个列表中取出 4 个元素，并检查它们是否符合条件.. 如果不符合.. 然后采用另一种组合

 var data = new List<List<int>>
            {
                new List<int> { 1,2 },
                new List<int> { 1,3 },
                new List<int> { 1,4 },
                new List<int> { 2,3 },
                new List<int> { 2,4 },
                new List<int> { 3,4 }
            };


  foreach (var picks in possiblePicks)
            {
                var listToTest = new List<List<int>>(4);
                foreach (var i in picks)
                    listToTest.Add(data[i]);

                var ok = Check(listToTest, 2);
                if (ok)
                    break;
            }



  private bool Check(List<List<int>> listToTest, int limit)
        {
            Dictionary<int, int> ret = new Dictionary<int, int>();
            foreach (var inputElem in listToTest)
            {
                foreach (var z in inputElem)
                {
                    var returnCount = ret.ContainsKey(z) ? ret[z] : 0;
                    if (!ret.ContainsKey(z))
                        ret.Add(z, returnCount + 1);
                    else
                        ret[z]++;
                }

            }
            return ret.All(p => p.Value == limit);
        }

我确信这可以进一步优化以最小化“listToTest”以外的迭代量

此外，这是一个惰性实现 (Ienumerable) - 因此如果碰巧第一个(或第二个)组合成功，它就会停止迭代。