配方（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循環變量）

回答

相關問題