带递归的变量 for 循环 [英] Variable for loops with recursion

问题描述

希望通过递归执行以下操作，以便我可以改变for"循环的数量:

n = 5出 = []对于范围(n)中的我:对于范围内的 j(i,n):对于范围内的 k(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 递归(n, p):# 其中 p 是 for 循环的次数一些魔法递归回来

我已经查看了其他一些递归问题，但很难找到解决方案.

解决方案

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

<预><代码>>>>导入迭代工具>>>列表(itertools.product(范围(3)，重复= 2))[(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)]>>>列表(itertools.product(范围(3)，重复= 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)]

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

defnested_loops(n, num_loops):prod = itertools.product(range(n), repeat=num_loops)对于产品中的项目:if all(item[i] <= item[i+1] for i in range(num_loops-1)):产量项目>>>列表(nested_loops(3, 2))[(0, 0), (0, 1), (0, 2), (1, 1), (1, 2), (2, 2)]>>>列表(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)]

Would like to do the following by recursion so that I can vary the number of 'for' loops:

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])

To return

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]...]

e.g.

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

I've had a look at some of the other recursion questions, but struggling to get to the solution.

解决方案

Instead of using recursion, use itertools.product(), which is equivalent to nested for loops in a generator expression:

>>> 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)]

edit: Didn't realize that this isn't actually a Cartesian product since the inner loops use the outer variable to start the range, here is one possibility but it is not as efficient as it could be because it generates extra values and needs to check that each value is valid:

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)]

这篇关于带递归的变量 for 循环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！