配方（for循环变量）

请考虑下面的算法：配方（for循环变量）

for(j1 = n upto 0) 
    for(j2 = n-j1 upto 0) 
     for(j3 = n-j1-j2 upto 0) 
     . 
     . 
      for (jmax = n -j1 - j2 - j_(max-1)) 
      { 
      count++; 
      product.append(j1 * j2 ... jmax); // just an example 
      }

正如你所看到的，对算法中的一些相关分片段上方：

我列出了算法的循环数可变。
我在每个最内层循环中计算的结果会附加到列表中。这个列表将会增加到“计数”的维度。

这个问题是否适合递归？如果是的话，我真的不知道如何解决问题。我试图在python中编写代码，我不希望你们有任何代码。只是一些指针或例子在正确的方向。谢谢。

下面是一个初步尝试了样品的情况下http://pastebin.com/PiLNTWED

来源

2013-04-24 hAcKnRoCk

看起来有一个函数，执行一个循环，然后调用自己做内部循环将是最直接的。 – 2013-04-24 13:50:54

[itertools.product]（http://docs.python.org/3/library/itertools.html#itertools.product） – JBernardo 2013-04-24 13:53:21

你的算法是找到所有m元组（m从你的伪代码是的j的max下标），加起来n以下非负整数。在Python，表达的是最自然的方法是用递归发生器：

输出示例：

>>> for x, y, z in gen_sums(3, 3): 
    print(x, y, z) 

3 0 0 
2 1 0 
2 0 1 
2 0 0 
1 2 0 
1 1 1 
1 1 0 
1 0 2 
1 0 1 
1 0 0 
0 3 0 
0 2 1 
0 2 0 
0 1 2 
0 1 1 
0 1 0 
0 0 3 
0 0 2 
0 0 1 
0 0 0

来源

2013-04-27 10:45:48 Blckknght

谢谢你的例子，虽然我需要不同的东西。为了查看对比并更具说明性，输出我的代码并输出为下面的答案。 – hAcKnRoCk 2013-04-27 11:52:07

@MhAcKNI：哦，你希望元组加起来正好是'n'，而不是'n'或更少。这实际上是我在编辑之前先执行的，以便与您的问题中的循环相匹配。为了得到你想要的，修改我的代码的基本大小写为'if m == 1：yield（n，）' – Blckknght 2013-04-27 12:42:27

玩具例如将转化为一种尾递归的话，就个人而言，我不希望一个递归版本是对代码审查和维护更深入。然而，为了了解这个原理，试图从单个循环中分解出不变的部分/常用术语，并试图找出一个模式（并且最好在事后证明它！）。您应该能够修复要写入的递归过程的签名。用循环体所固有的部分充实它（并且不要忘记终止条件）。

来源

2013-04-24 13:56:56 collapsar

您还可以考虑使用itertools模块中的排列组合或产品。如果你想I，J，K，...（即嵌套的for循环）的所有可能的组合，您可以使用：

for p in product(range(n), repeat=depth): 
    j1, j2, j3, ... = p # the same as nested for loops 
    # do stuff here

但要注意，迭代在循环的数量呈指数级增长！

来源

2013-04-24 13:59:16 jureslak

迭代次数不会是一个约束。我试图解决这个问题。将很快发布更新。 – hAcKnRoCk 2013-04-27 09:59:23

这里是一个简单的例子，当我知道深度[简单示例代码]（http://pastebin.com/PiLNTWED）。现在我不知道我怎么能把它翻译成itertools，当我不知道深度。 – hAcKnRoCk 2013-04-27 10:08:21

通常，如果要将for循环转换为递归调用，则需要用if语句替换for语句。对于嵌套循环，您将把它们转换为函数调用。

实践中，先从代码的哑变换开始，然后尝试查看以后可以优化的位置。

为了给你一个想法，尝试应用到你的情况，我会翻译是这样的：

results = [] 
for i in range(n): 
    results.append(do_stuff(i, n))

到这样的事情：

results = [] 

def loop(n, results, i=0): 
    if i >= n: 
     return results 
    results.append(do_stuff(i, n)) 
    i += 1 
    loop(n, results, i)

有不同的方式来处理返回结果列表，但你可以适应你的需求。

来源

2013-04-24 14:10:55 underrun

事情是我不知道'n'。其次，ith循环的循环变量取决于前一个（i-1）循环，依此类推。 – hAcKnRoCk 2013-04-24 23:49:36

- 至于由Blckgnht优秀上市的响应 - 考虑这里的n = 2且max = 3的情况

def simpletest():  

    ''' 
    I am going to just test the algo listing with assumption 
    degree n = 2 
    max = dim(m_p(n-1)) = 3, 
    so j1 j2 and upto j3 are required for every entry into m_p(degree2) 
    Lets just print j1,j2,j3 to verify if the function 
    works in other general version where the number of for loops is not known 
    ''' 
    n = 2 
    count = 0 
    for j1 in range(n, -1, -1): 
     for j2 in range(n -j1, -1, -1): 
      j3 = (n-(j1+j2)) 
      count = count + 1 
      print 'To calculate m_p(%d)[%d], j1,j2,j3 = ' %(n,count), j1, j2, j3 

    assert(count==6)  # just a checkpoint. See P.169 for a proof 
    print 'No. of entries =', count

该代码的输出（以及它是正确的）。

In [54]: %run _myCode/Python/invariant_hack.py 
To calculate m_p(2)[1], j1,j2,j3 = 2 0 0 
To calculate m_p(2)[2], j1,j2,j3 = 1 1 0 
To calculate m_p(2)[3], j1,j2,j3 = 1 0 1 
To calculate m_p(2)[4], j1,j2,j3 = 0 2 0 
To calculate m_p(2)[5], j1,j2,j3 = 0 1 1 
To calculate m_p(2)[6], j1,j2,j3 = 0 0 2 
No. of entries = 6

来源

2013-04-27 11:56:00 hAcKnRoCk

配方（for循环变量）

回答

相关问题