0

请考虑以下算法： 

  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
            }

如您所见，关于上述算法片段的一些相关点：

  1. 我列出了一个具有可变数量的 for 循环的算法。
  2. 我在每个最内层循环计算的结果被附加到一个列表中。该列表将增长到“计数”的维度。

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

这是示例案例http://pastebin.com/PiLNTWED的初步尝试

4

5 回答 5

1

您还可以考虑使用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-24T13:59:16.613 回答
1

您的算法正在查找加起来等于或小于的非负整数的所有m-tuples（m作为伪代码的max下标）。在 Python 中，最自然的表达方式是使用递归生成器：jn

def gen_tuples(m, n):
    if m == 0:
        yield ()
    else:
        for x in range(n, -1, -1):
            for sub_result in gen_tuples(m-1, n-x):
                yield (x,)+sub_result

示例输出：

>>> 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-27T10:45:48.150 回答
0

玩具示例将转化为一种尾递归，因此，就我个人而言，我不希望递归版本对代码审查和维护更有洞察力。

但是，要熟悉该原理，请尝试从单个循环中分解出不变的部分/常用术语并尝试识别模式（并最好在事后证明它！）。您应该能够修复要编写的递归过程的签名。用循环体固有的部分充实它（并且不要忘记终止条件）。

于 2013-04-24T13:56:56.250 回答
0

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

练习时，首先对有效的代码进行愚蠢的翻译，然后尝试查看以后可以优化的地方。

为了让您有一个想法尝试适用于您的情况，我会翻译如下内容：

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-24T14:10:55.100 回答
0

-- 作为对 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-27T11:56:00.273 回答