List<List<int>>的有序组合

Question

给定任意数量的有序列表

List<int> list1 = new List<int> {1, 1, 2};
List<int> list2 = new List<int> {1, 2, 3, 4};
List<int> list3 = new List<int> {1, 2};
List<int> listN = new List<int> {....,....};

我希望找到列表的组合，使得每个组合的总和按升序排列。例如：

{1, 1, 1} = 3, where {1 (1st element of list1), 1 (1st element of list2), 1 (1st element of list3)} 
{1, 1, 1} = 3, where {1 (2nd element of list1), 1 (1st element of list2, 1 (1st element of list3)}
{1, 2, 1} = 4
{1, 1, 2} = 4
{2, 1, 1} = 4
... 

找到升序求和的原因是我可以选择仅计算前M个组合（例如，上面的M = 5）。

我目前的想法是通过从列表的一个小子集开始，其中当前元素和下一个元素之间的差为0，来扩展查找所有列表的组合，如Combination of List<List<int>>中讨论的那样。

List<int> tempList1 = new List<int> {1, 1};
List<int> tempList2 = new List<int> {1};
List<int> tempList3 = new List<int> {1};

找到所有组合，然后将下一个具有最小差异的元素添加到列表中。

List<int> tempList1 = new List<int> {1, 1, 2};
List<int> tempList2 = new List<int> {1, 2};
List<int> tempList3 = new List<int> {1, 2};

从那里构建解决方案集是否可行？有更好的方法吗？

- wave

---

你是指对于每个被求和的列表进行组合后的总和吗？也就是说，您希望将每个列表中的所有数字求和，然后找到将这些总数相加得到的所有组合吗？ - Dave Bish

不完全正确。我想从list1、list2、...、listN中各取一个元素并求和，然后按这些总和排序。我将在原帖中的示例中尝试澄清这一点。 - wave

在你的例子中，有两种更多的方法可以得到总和为4，因为list1有两个相同的元素（两个1），所以我认为你的问题应该反映出来。 - Jeppe Stig Nielsen

Answer 1

试试这个：

List<int> list1 = new List<int> { 1, 1, 2 };
List<int> list2 = new List<int> { 1, 2, 3, 4 };
List<int> list3 = new List<int> { 1, 2 };

var combinations = list1
    .SelectMany(x => list2, (a, b) => new { a, b })
    .SelectMany(x => list3, (combined, c) => new { a = combined.a, b = combined.b, c })
    .Select(comb => new{ Sum = comb.a + comb.b + comb.c, Combination = new List<int>{comb.a, comb.b, comb.c}})
    .OrderBy(summed => summed.Sum);

╔═════════════╦═════╗
║ Combination ║ Sum ║
╠═════════════╬═════╣
║ 1,1,1       ║   3 ║
║ 1,1,1       ║   3 ║
║ 1,1,2       ║   4 ║
║ 1,2,1       ║   4 ║
║ 1,1,2       ║   4 ║
║ 1,2,1       ║   4 ║
╚═════════════╩═════╝

编辑：稍作整理

- Dave Bish

Answer 2

计算单个项目并不昂贵，但如果项目数量很大，则将所有结果保存在内存中并对其进行排序可能会很昂贵。然而，如果我理解正确，计算组合似乎对解决任务没有太大帮助。

编辑：当我开始撰写回答时，我没有看到关于组合的澄清。无论如何，如果您有不同组合的生成器，也可以使用以下算法。我不确定是否有通用解决方案仅生成所需的总和。

假设N是项目数，M是要获取的结果数。为了使以下内容有意义，我假设N >> M（例如，远远大于M）。

然后我会使用以下算法：

• 创建一个结果列表，最多可容纳M个项目。
• 遍历所有N个项目。
  • 对于每个项目，计算总数
  • 将总数插入结果列表中，以便顺序正确（二分搜索可能是用于执行此操作的良好算法）
  • 在插入后将结果列表修剪为不超过M个项目（插入的项目或先前插入的项目将根据其计算结果掉落）
• 现在您拥有按降序排序的前M个项目

请注意，如果您希望如此，可以轻松使上述算法与原始N项的顺序稳定相关。

- Lucero