是否可以从此函数中删除递归? [英] Is it possible to remove recursion from this function?
本文介绍了是否可以从此函数中删除递归?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我已经玩了一段时间了,只是找不到明显的解决方案.我想从 XinY_Go 函数中删除递归.
def XinY_Go(x,y,index,slots):如果(y - 索引)== 1:插槽[索引] = x打印槽插槽[索引] = 0返回对于范围内的 i (x+1):插槽[索引] = x-iXinY_Go(x-(x-i), y, index + 1, slot)def XinY(x,y):return XinY_Go(x,y,0,[0] * y)
该函数正在计算将 X 弹珠放入 Y 槽的方法数量.以下是一些示例输出:
<前>>>> xy.XinY(1,2)[1, 0][0, 1]>>> xy.XinY(2,3)[2, 0, 0][1, 1, 0][1, 0, 1][0, 2, 0][0, 1, 1][0, 0, 2] 解决方案
def XinY_Stack(x, y):堆栈 = [(x, 0, [0]*y)]而堆栈:x, 索引, 插槽 = stack.pop()如果(y - 索引)== 1:插槽[索引] = x打印槽插槽[索引] = 0别的:对于范围内的 i (x + 1):插槽[索引] = x-istack.append((i, index + 1, slot[:]))
示例:
<预><代码>>>>XinY_Stack(2, 3)[0, 0, 2][0, 1, 1][0, 2, 0][1, 0, 1][1, 1, 0][2, 0, 0]基于itertools.product
def XinY_Product(nmarbles, nslots):返回(插槽对于产品中的插槽(xrange(nmarbles + 1),repeat=nslots)if sum(slots) == nmarbles)
基于嵌套循环
def XinY_Iter(nmarbles, nslots):断言 0 静态嵌套块太多如果 nslots == 1: 返回 iter([nmarbles])# 为 iter 解决方案生成代码标签 = " "循环变量 = []stmt = ["def f(n):\n"]对于 i 在范围内(nslots - 1):var = "m%d" % istmt += [TAB * (i + 1), "对于 xrange(n - (%s)) 中的 %s:\n"% (var, '+'.join(loopvars) 或 0)]loopvars.append(var)stmt += [TAB * (i + 2), "yield ", ','.join(loopvars),', n - 1 - (', '+'.join(loopvars), ')\n']打印 ''.join(stmt)# 执行空命名空间内的代码ns = {}exec(''.join(stmt), ns, ns)返回 ns['f'](nmarbles + 1)
示例:
<预><代码>>>>列表(XinY_Product(2, 3))[(0, 0, 2), (0, 1, 1), (0, 2, 0), (1, 0, 1), (1, 1, 0), (2, 0, 0)]>>>列表(XinY_Iter(2, 3))定义 f(n):对于 xrange(n - (0)) 中的 m0:对于 xrange(n - (m0)) 中的 m1:产量 m0,m1, n - 1 - (m0+m1)[(0, 0, 2), (0, 1, 1), (0, 2, 0), (1, 0, 1), (1, 1, 0), (2, 0, 0)]I have been playing with this a while, and just cannot see an obvious solution. I want to remove the recursion from the XinY_Go function.
def XinY_Go(x,y,index,slots):
if (y - index) == 1:
slots[index] = x
print slots
slots[index] = 0
return
for i in range(x+1):
slots[index] = x-i
XinY_Go(x-(x-i), y, index + 1, slots)
def XinY(x,y):
return XinY_Go(x,y,0,[0] * y)
The function is calculating the number of ways to put X marbles in Y slots. Here is some sample output:
>>> xy.XinY(1,2) [1, 0] [0, 1] >>> xy.XinY(2,3) [2, 0, 0] [1, 1, 0] [1, 0, 1] [0, 2, 0] [0, 1, 1] [0, 0, 2]
解决方案
A naive implementation of @Joel Coehoorn's suggestion follows:
def XinY_Stack(x, y):
stack = [(x, 0, [0]*y)]
while stack:
x, index, slots = stack.pop()
if (y - index) == 1:
slots[index] = x
print slots
slots[index] = 0
else:
for i in range(x + 1):
slots[index] = x-i
stack.append((i, index + 1, slots[:]))
Example:
>>> XinY_Stack(2, 3)
[0, 0, 2]
[0, 1, 1]
[0, 2, 0]
[1, 0, 1]
[1, 1, 0]
[2, 0, 0]
Based on itertools.product
def XinY_Product(nmarbles, nslots):
return (slots
for slots in product(xrange(nmarbles + 1), repeat=nslots)
if sum(slots) == nmarbles)
Based on nested loops
def XinY_Iter(nmarbles, nslots):
assert 0 < nslots < 22 # 22 -> too many statically nested blocks
if nslots == 1: return iter([nmarbles])
# generate code for iter solution
TAB = " "
loopvars = []
stmt = ["def f(n):\n"]
for i in range(nslots - 1):
var = "m%d" % i
stmt += [TAB * (i + 1), "for %s in xrange(n - (%s)):\n"
% (var, '+'.join(loopvars) or 0)]
loopvars.append(var)
stmt += [TAB * (i + 2), "yield ", ','.join(loopvars),
', n - 1 - (', '+'.join(loopvars), ')\n']
print ''.join(stmt)
# exec the code within empty namespace
ns = {}
exec(''.join(stmt), ns, ns)
return ns['f'](nmarbles + 1)
Example:
>>> list(XinY_Product(2, 3))
[(0, 0, 2), (0, 1, 1), (0, 2, 0), (1, 0, 1), (1, 1, 0), (2, 0, 0)]
>>> list(XinY_Iter(2, 3))
def f(n):
for m0 in xrange(n - (0)):
for m1 in xrange(n - (m0)):
yield m0,m1, n - 1 - (m0+m1)
[(0, 0, 2), (0, 1, 1), (0, 2, 0), (1, 0, 1), (1, 1, 0), (2, 0, 0)]
这篇关于是否可以从此函数中删除递归?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文