2

想通过递归执行以下操作，以便我可以改变“for”循环的数量：

n = 5
out = []
for i in range(n):
    for j in range(i,n):
        for k in range(j,n):
            out.append([i,j,k])

返回

out =   [[0 0 0]
         [0 0 1]
         [0 0 2]
         [0 0 3]
         [0 0 4]
         [0 1 1]
         [0 1 2]
         [0 1 3]
         [0 1 4]
         [0 2 2]
         [0 2 3]
         [0 2 4]
         [0 3 3]
         [0 3 4]
         [0 4 4]
         [1 1 1]
         [1 1 2]
         [1 1 3]
         [1 1 4]
         [1 2 2]...]

例如

def Recurse(n, p):
  # where p is the number of for loops
  some magic recursion 
  return out

我看过其他一些递归问题，但很难找到解决方案。

4

2 回答 2

4

不使用递归，而是使用itertools.product()，这相当于生成器表达式中的嵌套 for 循环：

>>> import itertools
>>> list(itertools.product(range(3), repeat=2))
[(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)]
>>> list(itertools.product(range(3), repeat=3))
[(0, 0, 0), (0, 0, 1), (0, 0, 2), (0, 1, 0), (0, 1, 1), (0, 1, 2), (0, 2, 0), (0, 2, 1), (0, 2, 2), (1, 0, 0), (1, 0, 1), (1, 0, 2), (1, 1, 0), (1, 1, 1), (1, 1, 2), (1, 2, 0), (1, 2, 1), (1, 2, 2), (2, 0, 0), (2, 0, 1), (2, 0, 2), (2, 1, 0), (2, 1, 1), (2, 1, 2), (2, 2, 0), (2, 2, 1), (2, 2, 2)]

编辑：没有意识到这实际上不是笛卡尔积，因为内部循环使用外部变量来开始范围，这是一种可能性，但它的效率并不高，因为它会生成额外的值并且需要检查每个值是否有效：

def nested_loops(n, num_loops):
    prod = itertools.product(range(n), repeat=num_loops)
    for item in prod:
        if all(item[i] <= item[i+1] for i in range(num_loops-1)):
            yield item

>>> list(nested_loops(3, 2))
[(0, 0), (0, 1), (0, 2), (1, 1), (1, 2), (2, 2)]
>>> list(nested_loops(3, 3))
[(0, 0, 0), (0, 0, 1), (0, 0, 2), (0, 1, 1), (0, 1, 2), (0, 2, 2), (1, 1, 1), (1, 1, 2), (1, 2, 2), (2, 2, 2)]
于 2012-10-11T20:43:25.650 回答
2

@DSM 有更好的答案（但在评论中）

但是，这是一个简单的递归解决方案，以防万一有人努力解决

def f(n, p, start=0):
    if p==0:
        yield []
    else:
        for i in range(start, n):
            for j in f(n, p-1, i):
                yield [i]+j
于 2012-10-11T21:31:52.460 回答