c# - List> 的有序组合

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)。

我目前的想法是以某种方式扩展查找所有列表的组合，如 Combination of List<List<int>> 中所述。 ，从列表的一小部分开始，其中当前元素和下一个元素之间的差异为 0，例如

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

并从那里构建解决方案集。

这是否可能，是否有更好的方法来做到这一点？

Answer 1

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

编辑:当我开始写我的回复时，我没有看到关于组合的说明。无论哪种方式，如果您有不同组合的生成器，也可以使用以下算法。我不确定是否有一个通用的解决方案来只生成想要的总和。

假设 N 是项目数，M 是您想要获得的结果数。为了使下面的内容有意义，我假设 N >> M(例如大得多)。

然后我会使用以下算法:

• 创建最多包含 M 项的结果列表。
• 检查所有 N 项。
  • 计算每一项的总数
  • 在结果列表中插入总数，以便顺序正确(二分查找可能是一个很好的算法)
  • 插入后修剪结果列表不超过M项(插入的项，或之前插入的项，将根据它们的计算结果而掉落)
• 你现在有前 M 个项目，降序排列

请注意，如果需要，您可以轻松地使上述算法相对于原始 N 项的顺序稳定。