此问题与KenKen拉丁方谜题的某些部分有关，这些部分要求您查找具有值x的ncell数的所有可能组合，使得1 <= x <= maxval和x（1）+ … + x（ncells）= targetum。测试了一些更有希望的答案后，我将把答案奖授予Lennart Regebro，因为：
他的作息速度和我的一样快（+ -5％），并且
他指出，我原来的例程在某个地方有一个错误，这使我看到了它真正在试图做什么。谢谢，Lennart。
chrispy贡献了一种算法，该算法似乎与Lennart的算法相同，但是5个小时后，如此糟糕，首先要得到它。
备注：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)
首先，我将使用含义很深的变量名，以便使代码易于理解。然后，在我理解了这个问题之后，这显然是一个递归问题，因为一旦您选择了一个数字，寻找其余平方的可能值的问题就完全一样，只是其中的值不同。
所以我会这样：
from __future__ import division from math import ceil def make_combos(max_val,target_sum,n_cells): combos = [] # The highest possible value of the next cell is whatever is # largest of the max_val, or the target_sum minus the number # of remaining cells (as you can't enter 0). highest = min(max_val, target_sum - n_cells + 1) # The lowest is the lowest number you can have that will add upp to # target_sum if you multiply it with n_cells. lowest = int(ceil(target_sum/n_cells)) for x in range(highest, lowest-1, -1): if n_cells == 1: # This is the last cell, no more recursion. combos.append((x,)) break # Recurse to get the next cell: # Set the max to x (or we'll get duplicates like # (6,3,2,1) and (6,2,3,1), which is pointless. # Reduce the target_sum with x to keep the sum correct. # Reduce the number of cells with 1. for combo in make_combos(x, target_sum-x, n_cells-1): combos.append((x,)+combo) return combos if __name__ == '__main__': import pprint # And by using pprint the output gets easier to read pprint.pprint(make_combos( 6,12,4))
我还注意到您的解决方案似乎仍然有问题。例如，对于这些值，max_val=8, target_sum=20 and n_cells=5您的代码找不到解决方案(8,6,4,1,1,)。我不确定这是否意味着我错过了一条规则，但是据我了解，这些规则应该是有效的选择。
max_val=8, target_sum=20 and n_cells=5
(8,6,4,1,1,)
这是一个使用生成器的版本，如果值真的很大，它会节省几行代码和内存，但是作为递归，生成器“获取”可能很棘手。
from __future__ import division from math import ceil def make_combos(max_val,target_sum,n_cells): highest = min(max_val, target_sum - n_cells + 1) lowest = int(ceil(target_sum/n_cells)) for x in xrange(highest, lowest-1, -1): if n_cells == 1: yield (x,) break for combo in make_combos(x, target_sum-x, n_cells-1): yield (x,)+combo if __name__ == '__main__': import pprint pprint.pprint(list(make_combos( 6,12,4)))
