KenKen 拼图加法：REDUX A（修正后的）非递归算法
https://stackoverflow.com/questions/1061590
-
21-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
这个问题与 KenKen 拉丁方谜题的那些部分相关，这些部分要求您找到 ncells 数字与 x 值的所有可能组合，使得 1 <= x <= maxval 且 x(1) + ...+ x(ncells) = 目标和。在测试了几个更有希望的答案后，我将把答案奖授予 Lennart Regebro，因为：
他的日常动作和我的一样快（+-5%），并且
他指出我原来的例程在某个地方有一个错误，这让我明白了它真正想要做什么。谢谢，伦纳特。
chrispy 贡献了一种算法，看起来与 Lennart 的算法相当，但 5 小时后，很快，第一个电线就得到了它。
备注：Alex Martelli 的基本递归算法就是一个例子，它制作了所有可能的组合，然后将它们全部扔到筛子上，看看哪些可以穿过筛子。这种方法比 Lennart 或我的方法花费的时间要长 20 倍以上。（将输入设置为 max_val = 100、n_cells = 5、target_sum = 250，在我的盒子上，它是 18 秒 vs.8 分钟以上。）道德：不生成所有可能的组合是好的。
另一条评论：伦纳特和我的例程生成 相同的答案以相同的顺序. 。从不同角度看它们实际上是同一个算法吗？我不知道。
我突然想到一些事情。如果您对答案进行排序，例如，以 (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,), ， 举个例子。我不确定这是否意味着我错过了这方面的规则，但据我了解，这应该是一个有效的选项。
这是使用生成器的版本，如果值确实很大，它可以节省几行和内存，但作为递归，生成器可能很难“获取”。
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)))
其他提示
你的算法乍一看似乎相当不错，而且我不认为面向对象或其他语言会改进代码。我不能说递归是否有帮助，但我很欣赏非递归方法。我敢打赌，它更难工作，也更难阅读，但它可能更高效，而且绝对非常聪明。老实说，我没有详细分析该算法，但它看起来确实需要很长时间才能正常工作。我敢打赌，您必须考虑很多 1 误差和奇怪的边缘情况，是吗？
考虑到所有这些，基本上我想做的就是通过用更惯用的 Python 主义替换大量的 C 主义来尽我所能地美化你的代码。很多时候，C 中需要循环的事情可以在 Python 中用一行完成。我还尝试重命名一些东西以更好地遵循 Python 命名约定，并清理了一些注释。希望我的任何改变不会冒犯您。你可以拿走你想要的，留下其余的。:-)
以下是我工作时做的笔记：
- 修改了初始化的代码
tmp到一堆 1 到更惯用的tmp = [1] * n_cells. - 改变了
for总结的循环tmp_sum惯用语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))
这是我能想到的最简单的递归解决方案，“找到 n 个数字的所有可能组合，其值为 x，使得 1 <= x <= max_val 且 x(1) + ...+ x(n) = 目标”。我正在从头开始开发它。为了简单起见，这是一个根本没有任何优化的版本：
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 尝试“this”项的所有可能性，并循环遍历下一个较低级别的递归仍然能够产生的结果。
我看到的输出是：
(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》中正确引用了这句话，他告诉我这是从他父亲那里得到的，他的工作实际上与编程无关;-)。
在我看来，在这种情况下，关键问题是 理解 发生了什么，任何优化都可能会干扰，所以我全力以赴“简单易懂”；如果需要的话，我们可以在 OP 确认后立即进行优化 能 了解这个纯粹的、未经优化的版本中发生了什么！
抱歉，您的代码有点长，而且可读性不是很好。如果你可以尝试以某种方式总结它，也许有人可以帮助你写得更清楚。
至于问题本身，我的第一个想法是使用递归。（据我所知，你已经在这样做了。再次抱歉，我无法阅读您的代码。）想出一种方法，可以将问题简化为同一问题的更小更简单的版本，反复进行，直到您得到一个具有非常简单答案的小案例。
更具体一点，您有这三个参数：max_val、target_sum 和 n_cells。您能否将其中一个数字设置为某个特定值，以便为您提供一个根本不需要思考的极其简单的问题？一旦你有了这个，你能将问题的稍微困难的版本减少到已经解决的版本吗？
编辑：这是我的代码。我不喜欢它重复数据删除的方式。我确信还有一种更 Pythonic 的方式。此外，它不允许在一个组合中两次使用相同的数字。要撤消此行为，只需取出该行 if n not in numlist:. 。我不确定这是否完全正确，但它似乎有效并且（恕我直言）更具可读性。您可以轻松地添加记忆，这可能会大大加快速度。
def get_combos(max_val, target, n_cells):
if target <= 0:
return []
if n_cells is 1:
if target > max_val:
return []
else:
return [[target]]
else:
combos = []
for n in range(1, max_val+1, 1):
for numlist in get_combos(max_val, target-n, n_cells-1):
if n not in numlist:
combos.append(numlist + [n])
return combos
def deduplicate(combos):
for numlist in combos:
numlist.sort()
answer = [tuple(numlist) for numlist in combos]
return set(answer)
def kenken(max_val, target, n_cells):
return deduplicate(get_combos(max_val, target, n_cells))
首先，我自己正在学习Python，所以这个解决方案不会很好，但这只是解决这个问题的尝试。我尝试以递归方式解决它，我认为递归解决方案对于此类问题来说是理想的选择，尽管该递归解决方案可能不是这个：
def GetFactors(maxVal, noOfCells, targetSum):
l = []
while(maxVal != 0):
remCells = noOfCells - 1
if(remCells > 2):
retList = GetFactors(maxVal, remCells, targetSum - maxVal)
#Append the returned List to the original List
#But first, add the maxVal to the start of every elem of returned list.
for i in retList:
i.insert(0, maxVal)
l.extend(retList)
else:
remTotal = targetSum - maxVal
for i in range(1, remTotal/2 + 1):
itemToInsert = remTotal - i;
if (i > maxVal or itemToInsert > maxVal):
continue
l.append([maxVal, i, remTotal - i])
maxVal -= 1
return l
if __name__ == "__main__":
l = GetFactors(5, 5, 15)
print l
这是 C/C++ 中的简单解决方案：
const int max = 6;
int sol[N_CELLS];
void enum_solutions(int target, int n, int min) {
if (target == 0 && n == 0)
report_solution(); /* sol[0]..sol[N_CELLS-1] is a solution */
if (target <= 0 || n == 0) return; /* nothing further to explore */
sol[n - 1] = min; /* remember */
for (int i = min; i <= max; i++)
enum_solutions(target - i, n - 1, i);
}
enum_solutions(12, 4, 1);
有点离题，但仍然可能对 kenken 编程有所帮助。
我使用 DLX 算法求解 Killer Sudoku 得到了很好的结果（与 KenKen 非常相似，它有笼子，但只有求和）。大多数问题的处理时间不到一秒，并且是用 MATLAB 语言实现的。
参考这个论坛http://www.setbb.com/phpbb/viewtopic.php?t=1274&highlight=&mforum=sudoku
杀手数独 “看看维基百科，不能发布超链接”的垃圾邮件发送者
这是一个使用生成器的简单但简洁的解决方案：
def descending(v):
"""Decide if a square contains values in descending order"""
return list(reversed(v)) == sorted(v)
def latinSquares(max_val, target_sum, n_cells):
"""Return all descending n_cells-dimensional squares,
no cell larger than max_val, sum equal to target_sum."""
possibilities = itertools.product(range(1,max_val+1),repeat=n_cells)
for square in possibilities:
if descending(square) and sum(square) == target_sum:
yield square
我可以通过直接枚举降序网格列表来优化此代码，但我发现 itertools.product 对于首次解决方案来说更加清晰。最后，调用该函数：
for m in latinSquares(6, 12, 4):
print m
这是另一个基于生成器的递归解决方案，但这次使用一些简单的数学来计算每一步的范围，避免不必要的递归：
def latinSquares(max_val, target_sum, n_cells):
if n_cells == 1:
assert(max_val >= target_sum >= 1)
return ((target_sum,),)
else:
lower_bound = max(-(-target_sum / n_cells), 1)
upper_bound = min(max_val, target_sum - n_cells + 1)
assert(lower_bound <= upper_bound)
return ((v,) + w for v in xrange(upper_bound, lower_bound - 1, -1)
for w in latinSquares(v, target_sum - v, n_cells - 1))
如果您提供无法满足的参数，此代码将失败并出现断言错误；这是我的“正确性标准”的副作用，即我们从不进行不必要的递归。如果您不希望出现这种副作用，请删除断言。
请注意除法后使用 -(-x/y) 进行舍入。可能有一种更Pythonic的方式来编写它。另请注意我正在使用 生成器表达式 而不是产量。
for m in latinSquares(6,12,4):
print m
