문제
나는 이것을 오랫동안 가지고 놀았으며, 명백한 해결책을 볼 수는 없습니다. xiny_go 함수에서 재귀를 제거하고 싶습니다.
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)
이 기능은 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]
해결책
순진한 구현 @Joel Coehoorn의 제안 다음 :
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[:]))
예시:
>>> 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):
return (slots
for slots in product(xrange(nmarbles + 1), repeat=nslots)
if sum(slots) == nmarbles)
중첩 루프를 기반으로합니다
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)
예시:
>>> 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)]
다른 팁
재귀로 생각하는 모든 것은 스택 기반 문제로 생각할 수 있습니다. 여기서 재귀 함수는 별도의 스택을 만드는 대신 프로그램의 통화 스택을 사용합니다. 즉, 스택을 사용하여 재귀 함수를 다시 작성할 수 있습니다.
나는 당신에게 구현을 줄만큼 충분히 파이썬을 잘 모르지만, 그것은 당신을 올바른 방향으로 지적해야합니다. 그러나 간단히 말해서 함수의 초기 인수를 스택에 밀어 넣고 스택의 크기가 0보다 크면 실행되는 루프를 추가하십시오. 루프 반복 당 한 번 팝하면 기능이 현재 호출 할 때마다 푸시하십시오.
모든 순열을 만들기 위해이 코드를 살펴보면 문제와 비슷한 것을 구현하는 것이 비교적 간단하다고 생각합니다.
제휴하지 않습니다 StackOverflow