背景
嗨,我正在尝试解决一个编程问题,以下是我卡在的问题:
假设您有多个数字列表。所有列表都按递减顺序排序。 现在,您必须从每个列表中取一个数字,以使总和最大。
到此为止还很简单,要解决这个问题,您只需要从每个列表中取出第一个数字即可。
但是,现在我需要第二大的总和,仍然只能从每个列表中选取一个数字。 为了实现这一点,我将从每个列表中选择第一个元素,但对于差异最小的第一个和第二个数字之间的列表,将使用第二个数字。
这仍然相当容易。
问题
但我需要一个迭代器,可以对每个可能的总和进行迭代,每个列表只用选择一个数字并按递减顺序排序。
出于性能原因,不可能计算每个总和然后对其进行排序。算法必须已经按递减顺序提供总和。如果有多个组合可以得到该总和,则必须多次返回该总和。
附加要求
迭代器应该是惰性的(仅在需要时才计算下一个总和)。
列表已经是惰性的,这意味着您应该尽量少地要求计算适合的和。
示例
对于以下列表:
List 1: [5, 2, 1]
List 2: [10, 2]
List 3: [6, 1]
迭代器应该返回:
[5, 10, 6] = 21
[2, 10, 6] = 18
[1, 10, 6] = 17
[5, 10, 1] = 16
[5, 2, 6] = 13
[2, 10, 1] = 13
[1, 10, 1] = 12
[2, 2, 6] = 10
[1, 2, 6] = 9
[5, 2, 1] = 8
[2, 2, 1] = 5
[1, 2, 1] = 4
评论
我不需要代码作为我的问题的答案(如果它有助于解释,您仍然可以提供)。我正在寻找解决这个问题的想法,或者我可以自己实现的解决方案。
提前感谢!