KenKen谜题加数：redux A（修正）非递归算法
这个问题和KenKen拉丁方块谜题中的一些部分有关，这些部分要求你找到所有可能的组合，组合中有ncells个数字，这些数字的值在1到maxval之间，并且这些数字的总和等于targetsum。我测试了几个比较有希望的答案，最终决定把答案的奖励给Lennart Regebro，因为：
他的程序运行速度和我的差不多（大约快5%），
他指出了我原来的程序中有个bug，这让我意识到它实际上是想做什么。谢谢你，Lennart。
chrispy也提供了一个算法，似乎和Lennart的算法是等效的，但他晚了5个小时，所以，先到先得。
还有一点要提：Alex Martelli的简单递归算法是一个生成所有可能组合的例子，然后把这些组合放到一个筛子里，看看哪些能通过。这种方法的运行时间比Lennart的或我的慢20倍以上。（如果把输入提高到max_val=100，n_cells=5，target_sum=250，在我的电脑上，运行时间是18秒对比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)
9 个回答
这是我能想到的最简单的递归解决方案，用来“找到所有可能的组合，包含n个数字，值为x，满足1 <= x <= max_val，并且x(1) + ... + x(n) = target”。我正在从零开始开发这个方案。下面是一个没有任何优化的版本，仅仅为了简单明了：
def apcnx(n, max_val, target, xsofar=(), sumsofar=0):
if n==0:
if sumsofar==target:
yield xsofar
return
if xsofar:
minx = xsofar[-1] - 1
else:
minx = 0
for x in xrange(minx, max_val):
for xposs in apcnx(n-1, max_val, target, xsofar + (x+1,), sumsofar+x+1):
yield xposs
for xs in apcnx(4, 6, 12):
print xs
基本情况是n==0（也就是说我们不能再生成更多的数字），如果当前的组合满足条件，就返回这个组合，否则就什么也不返回，然后结束（返回）。
如果我们需要生成比当前组合更长的组合，if/else确保我们只生成不递减的组合，以避免重复（你是说“组合”而不是“排列”）。
for循环尝试“这个”项目的所有可能性，并遍历下一个更低层级的递归能生成的内容。
我看到的输出是：
(1, 1, 4, 6)
(1, 1, 5, 5)
(1, 2, 3, 6)
(1, 2, 4, 5)
(1, 3, 3, 5)
(1, 3, 4, 4)
(2, 2, 2, 6)
(2, 2, 3, 5)
(2, 2, 4, 4)
(2, 3, 3, 4)
(3, 3, 3, 3)
看起来是正确的。
有很多可能的优化方法，但请记住：
先让它工作，然后再让它快
我和Kent Beck联系过，想要正确引用这句话，出自《Python in a Nutshell》，他告诉我这句话是他从他爸爸那里学来的，而他爸爸的工作和编程其实没有关系;-)。
在这种情况下，我觉得关键问题是理解发生了什么，任何优化可能会干扰这个过程，所以我会尽量保持“简单易懂”；如果需要的话，我们可以在原作者确认他们能理解这个完全没有优化的版本后，再进行各种优化！
你的算法一开始看起来不错，我觉得用面向对象的语言或者其他语言也不会让代码变得更好。我不能确定递归是否会有帮助，但我很欣赏你用非递归的方法。我敢打赌，这种方法更难实现，而且阅读起来也更费劲，但它可能更高效，确实很聪明。老实说，我没有详细分析这个算法，但看起来你花了很长时间才把它搞定。我敢肯定你遇到了很多越界错误和奇怪的边界情况需要考虑，对吧？
基于这些，我基本上只是尽量把你的代码美化了一下，把很多C语言的写法换成更符合Python习惯的写法。通常在C语言中需要用循环的地方，在Python中可以用一行代码搞定。此外，我还试着把一些变量名改得更符合Python的命名规范，并稍微整理了一下注释。希望我的修改没有让你不高兴。你可以选择接受我的修改，也可以不采纳。:-)
以下是我在工作时记录的笔记：
- 把初始化
tmp为一堆1的代码改成了更符合习惯的tmp = [1] * n_cells。 - 把计算
tmp_sum的for循环改成了更简洁的sum(tmp)。 - 然后把所有的循环替换成了
tmp = <list> + <list>的一行代码。 - 把
raise doneException移动到了init_tmp_new_ceiling中，并去掉了succeeded这个标志。 - 在
init_tmp_new_ceiling中的检查似乎是多余的。去掉它后，剩下的raise只在make_combos_n_cells中，所以我把它们改成了普通的返回，并完全去掉了doneException。 - 统一了缩进，4个空格和8个空格混用的问题。
- 去掉了
if条件周围不必要的括号。 tmp[p2] - tmp[p1] == 0和tmp[p2] == tmp[p1]是一样的。- 把
while True: if new_ceiling_flag: break改成了while not new_ceiling_flag。 - 你不需要在函数开头把变量初始化为0。
- 去掉了
combos列表，改成在生成元组时直接yield它们。 - 把
tmp改名为combo。 - 把
new_ceiling_flag改名为ceiling_changed。
这是我整理后的代码，供你参考：
def initial_combo(ceiling=5, target_sum=13, num_cells=4):
"""
Returns a list of possible addends, probably to be modified further.
Starts a new combo list, then, starting from left, fills items to ceiling
or intermediate between 1 and ceiling or just 1. E.g.:
Given ceiling = 5, target_sum = 13, num_cells = 4: creates [5,5,2,1].
"""
num_full_cells = (target_sum - num_cells) // (ceiling - 1)
combo = [ceiling] * num_full_cells \
+ [1] * (num_cells - num_full_cells)
if num_cells > num_full_cells:
combo[num_full_cells] += target_sum - sum(combo)
return combo
def all_combos(ceiling, target_sum, num_cells):
# p0 points at the rightmost item and moves left under some conditions
# p1 starts out at rightmost items and steps left
# p2 starts out immediately to the left of p1 and steps left as p1 does
# So, combo[p2] and combo[p1] always point at a pair of adjacent items.
# d combo[p2] - combo[p1]; immediate difference
# cd combo[p2] - combo[p0]; cumulative difference
# The ceiling decreases by 1 each iteration.
while True:
combo = initial_combo(ceiling, target_sum, num_cells)
yield tuple(combo)
ceiling_changed = False
# Generate all of the remaining combos with this ceiling.
while not ceiling_changed:
p2, p1, p0 = -2, -1, -1
while combo[p2] == combo[p1] and abs(p2) <= num_cells:
# 3,3,3,3
if abs(p2) == num_cells:
return
p2 -= 1
p1 -= 1
p0 -= 1
cd = 0
# slide_ptrs_left loop
while abs(p2) <= num_cells:
d = combo[p2] - combo[p1]
cd += d
# 5,5,3,3 or 5,5,4,3
if cd > 1:
if abs(p2) < num_cells:
# 5,5,3,3 --> 5,4,4,3
if d > 1:
combo[p2] -= 1
combo[p1] += 1
# d == 1; 5,5,4,3 --> 5,4,4,4
else:
combo[p2] -= 1
combo[p0] += 1
yield tuple(combo)
# abs(p2) == num_cells; 5,4,4,3
else:
ceiling -= 1
ceiling_changed = True
# Resume at make_combo_same_ceiling while
# and follow branch.
break
# 4,3,3,3 or 4,4,3,3
elif cd == 1:
if abs(p2) == num_cells:
return
p1 -= 1
p2 -= 1
if __name__ == '__main__':
print list(all_combos(ceiling=6, target_sum=12, num_cells=4))
首先，我会使用一些有意义的变量名，这样代码就容易理解了。然后，在我搞清楚问题后，发现这明显是一个递归问题，因为一旦你选择了一个数字，接下来要找其他方格的可能值，其实就是同样的问题，只是用不同的数字而已。
所以我会这样做：
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 和 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)))