这个问题与 KenKen 拉丁方谜题的那些部分有关，这些部分要求您找到 ncells 数字的所有可能组合，其值为 x 使得 1 <= x <= maxval 和 x(1) + ... + x(ncells) =目标总和。在测试了几个更有希望的答案之后，我将把答案奖授予 Lennart Regebro，因为：
他的例行程序和我的一样快（+-5%），并且
他指出我原来的例程在某个地方有一个错误，这让我看到了它真正想要做什么。谢谢，伦纳特。
chrispy 贡献了一个似乎与 Lennart 相当的算法，但 5 小时后，sooo，第一个得到它。
备注：Alex Martelli 的基本递归算法是一个示例，它制作了所有可能的组合并将它们全部扔到筛子上，看看哪个穿过了孔。这种方法比 Lennart 或我的方法花费的时间要长 20 倍以上。（将输入提升到 max_val = 100，n_cells = 5，target_sum = 250，在我的盒子上是 18 秒 vs. 8+ 分钟。） 道德：不生成所有可能的组合是好的。
另一句话：Lennart 和我的例程以相同的顺序生成相同的答案。它们实际上是从不同角度看到的相同算法吗？我不知道。
我发生了什么事。如果您对答案进行排序，例如，以 (8,8,2,1,1) 开头并以 (4,4,4,4,4) 结尾（max_val=8, n_cells=5, target_sum =20），该系列形成一种“最慢下降”，第一个是“热”，最后一个是“冷”，中间有尽可能多的阶段。这与“信息熵”有关吗？观察它的正确指标是什么？是否有一种算法可以按热量的降序（或升序）产生组合？（据我所见，这个没有，尽管它在很短的时间内很接近，看着标准化的标准开发。）
这是 Python 例程：
#!/usr/bin/env python
#filename: makeAddCombos.07.py -- stripped for StackOverflow
def initialize_combo( max_val, n_cells, target_sum):
"""returns combo
Starting from left, fills combo to max_val or an intermediate value from 1 up.
E.g.: Given max_val = 5, n_cells=4, target_sum = 11, creates [5,4,1,1].
"""
combo = []
#Put 1 in each cell.
combo += [1] * n_cells
need = target_sum - sum(combo)
#Fill as many cells as possible to max_val.
n_full_cells = need //(max_val - 1)
top_up = max_val - 1
for i in range( n_full_cells): combo[i] += top_up
need = target_sum - sum(combo)
# Then add the rest to next item.
if need > 0:
combo[n_full_cells] += need
return combo
#def initialize_combo()
def scrunch_left( combo):
"""returns (new_combo,done)
done Boolean; if True, ignore new_combo, all done;
if Falso, new_combo is valid.
Starts a new combo list. Scanning from right to left, looks for first
element at least 2 greater than right-end element.
If one is found, decrements it, then scrunches all available counts on its
right up against its right-hand side. Returns the modified combo.
If none found, (that is, either no step or single step of 1), process
done.
"""
new_combo = []
right_end = combo[-1]
length = len(combo)
c_range = range(length-1, -1, -1)
found_step_gt_1 = False
for index in c_range:
value = combo[index]
if (value - right_end) > 1:
found_step_gt_1 = True
break
if not found_step_gt_1:
return ( new_combo,True)
if index > 0:
new_combo += combo[:index]
ceil = combo[index] - 1
new_combo += [ceil]
new_combo += [1] * ((length - 1) - index)
need = sum(combo[index:]) - sum(new_combo[index:])
fill_height = ceil - 1
ndivf = need // fill_height
nmodf = need % fill_height
if ndivf > 0:
for j in range(index + 1, index + ndivf + 1):
new_combo[j] += fill_height
if nmodf > 0:
new_combo[index + ndivf + 1] += nmodf
return (new_combo, False)
#def scrunch_left()
def make_combos_n_cells_ge_two( combos, max_val, n_cells, target_sum):
"""
Build combos, list of tuples of 2 or more addends.
"""
combo = initialize_combo( max_val, n_cells, target_sum)
combos.append( tuple( combo))
while True:
(combo, done) = scrunch_left( combo)
if done:
break
else:
combos.append( tuple( combo))
return combos
#def make_combos_n_cells_ge_two()
if __name__ == '__main__':
combos = []
max_val = 8
n_cells = 5
target_sum = 20
if n_cells == 1: combos.append( (target_sum,))
else:
combos = make_combos_n_cells_ge_two( combos, max_val, n_cells, target_sum)
import pprint
pprint.pprint( combos)