啃啃拼图加数：REDUX A（修正）的非递归算法 [英] KenKen puzzle addends: REDUX A (corrected) non-recursive algorithm
问题描述
这个问题涉及啃啃拉丁广场拼图这要求你找到ncells数字的所有可能的组合与值x，使得1 LT的部分; = X＆LT; = MAXVAL和X（1）+ ... + X（ncells）= targetsum。已经测试了几个比较有希望的答案，我要奖励的答案 - 奖伦纳特Regebro，因为：
-
他的程序是一样快，我的（±5％），以及
-
他指出，我原来的程序有错误的地方，这使我明白它真正想要做的事情。谢谢你，伦纳特。
chrispy贡献的算法，似乎等同于梅里的，但5小时后，SOOO，先以导线变了。
中的一句话：亚历克斯·马尔泰利的裸机递归算法是使每一个可能的组合，并把他们所有的筛子又看见经过洞的一个例子。这种方法花费的时间比伦纳特的还是我的20+倍。 （抬高输入到MAX_VAL = 100，n_cells = 5，target_sum = 250，并在我的箱子是18秒与8 +分钟）道德：不产生每一个可能的组合是不错
另一句话：伦纳德和我的程序产生的以相同的顺序相同的答案。难道他们其实同样的算法，从不同的角度看到的？我不知道。
事情发生在我身上。如果排序的答案，首先，比方说，用（8,8,2,1,1）和（4,4,4,4,4）（就是你得到的与MAX_VAL = 8，n_cells = 5，target_sum结束= 20），该系列形成种类的最慢的下降，与第一的莫过于热，最后一个是冷和阶段的中间可能的最大数目。这是与信息熵？什么是正确的量度看它？是否有一个算法，中制成的组合，下降（或上升）的热秩序？ （这其中没有，据我所看到的，虽然它是接近在短绵延，看着规范化性病。dev的。）
下面是Python的程序：
＃！的/ usr /斌/包膜蟒蛇
#filename：makeAddCombos.07.py - 剥去计算器
高清initialize_combo（MAX_VAL，n_cells，target_sum）：
回报组合
从左边开始，填充组合到MAX_VAL或从1的中间值。
例如：鉴于MAX_VAL = 5，n_cells = 4，target_sum = 11，创建[5,4,1,1]。
组合= []
#Put 1每个单元中。
组合+ = [1] * n_cells
需要= target_sum - 总和（组合）
#Fill尽可能多的细胞可能MAX_VAL。
n_full_cells =需要//（MAX_VAL - 1）
top_up = MAX_VAL - 1
因为我在范围内（n_full_cells）：组合[I] + = top_up
需要= target_sum - 总和（组合）
＃那么剩下添加到下一个项目。
如果需要＆GT; 0：
组合[n_full_cells] + =必要
收益组合
#def initialize_combo（）
高清scrunch_left（组合）：
回报（new_combo，完成）
完成布尔;如果是真的，忽略new_combo，全部完成;
如果FALSO，new_combo是有效的。
启动一个新的组合列表。从右到左扫描，寻找第一个
元素比右端的元素至少有2大。
如果找到一个，它递减，那么scrunches上的所有可用计数其
正对着它的右侧。返回修改后的组合。
如果没有发现，（即，要么没有台阶或1单步），过程
完成。
new_combo = []
right_end =组合[-1]
长度= LEN（组合）
c_range =范围（长度-1，-1，-1）
found_step_gt_1 =假
对于指数c_range：
值=组合[指数]
如果（价值 - right_end）＆GT; 1：
found_step_gt_1 = TRUE
打破
如果不是found_step_gt_1：
返程（new_combo，真）
如果索引＆gt; 0：
new_combo + =组合[：索引]
CEIL =组合[指数] - 1
new_combo + = [CEIL]
new_combo + = [1] *（（长度 - 1） - 指数）
需要= SUM（组合[指数：]） - 和（new_combo [指数：]）
fill_height = CEIL - 1
ndivf =需要// fill_height
nmodf =需要％fill_height
如果ndivf＆GT; 0：
对于j的范围（索引+ 1，索引+ ndivf + 1）：
new_combo [J] + = fill_height
如果nmodf＆GT; 0：
new_combo [指数+ ndivf + 1] + = nmodf
返程（new_combo，FALSE）
#def scrunch_left（）
高清make_combos_n_cells_ge_two（连击，MAX_VAL，n_cells，target_sum）：
构建连击，2个或更多的加数的元组列表。
组合= initialize_combo（MAX_VAL，n_cells，target_sum）
combos.append（元组（组合））
而真正的：
（二合一，做）= scrunch_left（组合）
如果这样做：
打破
其他：
combos.append（元组（组合））
返回组合
#def make_combos_n_cells_ge_two（）
如果__name__ =='__main__'：
组合= []
MAX_VAL = 8
n_cells = 5
target_sum = 20
如果n_cells == 1：combos.append（（target_sum，））
其他：
连击= make_combos_n_cells_ge_two（连击，MAX_VAL，n_cells，target_sum）
进口pprint
pprint.pprint（组合）
首先，我会使用的变量名意味着什么，从而使code得到COM prehensible。然后，当我明白这个问题，这显然是一个递归问题，因为一旦你选择了一个号码，找到可能的值的平方剩下的问题是完全一样的问题，但在不同的值。
所以，我会做这样的：
从__future__进口师
从数学进口CEIL
高清make_combos（MAX_VAL，target_sum，n_cells）：
组合= []
＃下一个单元格可能达到的最高值就是为
＃最大的MAX_VAL或target_sum减去数
＃剩余的细胞（如不能输入0）。
最高=分钟（MAX_VAL，target_sum - n_cells + 1）的
＃最低的是你可以有，将增加UPP来最低的数字
＃target_sum如果你n_cells相乘。
最低= INT（CEIL（target_sum / n_cells））
x的范围（最高，最低-1，-1）：
如果n_cells == 1：＃这是最后一个单元格，没有更多的递归。
combos.append（（X，））
打破
＃递归以获得下一个单元格：
＃设置最大为x（否则我们会获得一个类似副本
＃（6,3,2,1）和（6,2,3,1），这是没有意义的。
＃减少与X中的target_sum保持总和正确。
＃减少细胞的数目为1。
对于组合在make_combos（X，target_sum-X，n_cells-1）：
combos.append（（X，）+ COMBO）
返回组合
如果__name__ =='__main__'：
进口pprint
＃并使用pprint输出变得更容易阅读
pprint.pprint（make_combos（6,12,4））
我还注意到，您的解决方案似乎仍然马车。对于值 MAX_VAL = 8，target_sum = 20，n_cells = 5 您code没有找到解决办法（8,6,4 ，1,1，），系统，例如，我不知道如果这意味着我已经错过了一个规则在这个与否，但据我所知的规则，应该是一个有效的选择。
下面是一个使用发电机的一个版本，它节省了几行，并且内存，如果值是非常大的，但作为递归，发电机可能会非常棘手搞定。
从__future__进口师
从数学进口CEIL
高清make_combos（MAX_VAL，target_sum，n_cells）：
最高=分钟（MAX_VAL，target_sum - n_cells + 1）的
最低= INT（CEIL（target_sum / n_cells））
对于x中的xrange（最高，最低-1，-1）：
如果n_cells == 1：
收益率（X，）
打破
对于组合在make_combos（X，target_sum-X，n_cells-1）：
收益率（X，）+连击
如果__name__ =='__main__'：
进口pprint
pprint.pprint（名单（make_combos（6,12,4）））
This question relates to those parts of the KenKen Latin Square puzzles which ask you to find all possible combinations of ncells numbers with values x such that 1 <= x <= maxval and x(1) + ... + x(ncells) = targetsum. Having tested several of the more promising answers, I'm going to award the answer-prize to Lennart Regebro, because:
his routine is as fast as mine (+-5%), and
he pointed out that my original routine had a bug somewhere, which led me to see what it was really trying to do. Thanks, Lennart.
chrispy contributed an algorithm that seems equivalent to Lennart's, but 5 hrs later, sooo, first to the wire gets it.
A remark: Alex Martelli's bare-bones recursive algorithm is an example of making every possible combination and throwing them all at a sieve and seeing which go through the holes. This approach takes 20+ times longer than Lennart's or mine. (Jack up the input to max_val = 100, n_cells = 5, target_sum = 250 and on my box it's 18 secs vs. 8+ mins.) Moral: Not generating every possible combination is good.
Another remark: Lennart's and my routines generate the same answers in the same order. Are they in fact the same algorithm seen from different angles? I don't know.
Something occurs to me. If you sort the answers, starting, say, with (8,8,2,1,1) and ending with (4,4,4,4,4) (what you get with max_val=8, n_cells=5, target_sum=20), the series forms kind of a "slowest descent", with the first ones being "hot" and the last one being "cold" and the greatest possible number of stages in between. Is this related to "informational entropy"? What's the proper metric for looking at it? Is there an algorithm that producs the combinations in descending (or ascending) order of heat? (This one doesn't, as far as I can see, although it's close over short stretches, looking at normalized std. dev.)
Here's the Python routine:
#!/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)
First of all, I'd use variable names that mean something, so that the code gets comprehensible. Then, after I understood the problem, it's clearly a recursive problem, as once you have chosen one number, the question of finding the possible values for the rest of the squares are exactly the same problem, but with different values in.
So I would do it like this:
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))
I also notice that your solution still seems buggy. For the values max_val=8, target_sum=20 and n_cells=5 your code doesn't find the solution (8,6,4,1,1,), as an example. I'm not sure if that means I've missed a rule in this or not, but as I understand the rules that should be a valid option.
Here's a version using generators, It saves a couple of lines, and memory if the values are really big, but as recursion, generators can be tricky to "get".
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)))
这篇关于啃啃拼图加数：REDUX A（修正）的非递归算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
