2011-03-16 122 views
1

這個堆棧溢出線程聲稱每個遞歸函數都可以寫成一個循環。如何重寫遞歸函數來代替使用循環?

Which recursive functions cannot be rewritten using loops?

它使完整意義上的。但我不知道如何將下面的遞歸函數表示爲循環,因爲它有一個預先遞歸的邏輯和後遞歸邏輯。

很明顯,該解決方案無法使用goto語句。該代碼是在這裏:

def gen_perms(lst, k, m): 

    if k == m: 
     all_perms.append(list(lst)) 
    else: 
     for i in xrange(k, m+1): 

      #swap char 
      tmp = lst[k] 
      lst[k] = lst[i] 
      lst[i] = tmp 

      gen_perms(lst, k+1, m) 

      #swap char 
      tmp = lst[k] 
      lst[k] = lst[i] 
      lst[i] = tmp 

調用它會是這樣:

all_perms = [] 
gen_perm([1, 2, 3], 0, 2) 

和它產生的列表1,2,3的每一個排列。

+1

@nmichaels:Python沒有goto語句。 – 2011-03-16 18:59:33

+0

個人...我認爲它可以解決,但你需要引用一些變量來管理你的遞歸在一個循環內執行的事實...因此你需要存儲循環的位置和你通過遞歸...「變成」或「變成」可以這麼說。 – Philluminati 2011-03-16 19:06:18

+1

是的,你可以使用相同的算法並假裝成解釋器並管理自己的堆棧。或者,你可以想出一個用於生成排列的迭代算法,這將更容易表達爲循環。 – nmichaels 2011-03-16 19:08:44

回答

0

我不太熟悉python語法,但是下面的代碼(在'c'中)不應該太難轉換,假設python可以嵌套語句。

int list[3]={1,2,3}; 
int i,j,k; 

for(i=0;i < SIZE;i++) 
for(j=0;j < SIZE;j++) 
for(k=0;k < SIZE;k++) 
if(i!=j && j!=k && i!=k) 
printf("%d%d%d\n",list[i],list[j],list[k]); 
+0

這樣做是否行得通,因爲每個數字都有一個索引......即。如果列表大小爲4,我需要另一個循環嗎? – Philluminati 2011-03-16 20:28:55

+0

是的,這隻適用於列表大小爲3的情況。我對此類遲到的評論表示歉意。 – Adam 2011-03-17 02:58:23

3

做置換的最Python的方式是使用:

>>> from itertools import permutations 
>>> permutations([1,2,3]) 
>>> list(permutations([1,2,3])) 
[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)] 
+0

該函數的文檔顯示瞭如何迭代生成排列:http://docs.python.org/py3k/library/itertools#itertools.permutations – ncoghlan 2011-03-16 19:26:00

+0

這似乎不適用於我。我可以在Python 2.5.2中導入itertools,但我沒有排列函數 – Philluminati 2011-03-16 19:29:04

+0

@Philluminati來自版本2.6 – fabrizioM 2011-03-16 20:53:32

1

比方說,你想找到的所有排列[1,2,3,4]。有24(= 4!)這些,所以數字0-23。我們想要的是找到第N個排列的非遞歸方式。

假設我們按增加的數字順序對排列進行排序。然後:

  • 排列置換0-5從1開始
  • 排列置換6-11開始用2
  • 排列組合12-17開始與3
  • 排列組合18-23開始與4

所以我們可以通過N除以6(= 3!)得到第一個置換數N,然後四捨五入。

我們如何得到下一個數字?看第二號碼排列0-5:

  • 排列置換0-1具有第二數量2.
  • 排列置換2-3具有第二數量3.
  • 排列置換4-5具有第二數目4。

我們看到排列6-11類似的事情:

  • 排列組合6-7有第二個數字1
  • 排列組合8-9具有第二數量3.
  • 排列組合10-11具有第二數目4.

一般而言,取餘數由6較早劃分後,除以2(= 2!) ,並收起來。這會給你1,2或3,第二項是列表中剩下的第一,第二或第三項(在你取出第一項後)。

你可以繼續這樣。這裏有一些代碼是這樣的:

from math import factorial 

def gen_perms(lst): 
    all_perms = [] 

    # Find the number of permutations. 
    num_perms = factorial(len(lst)) 

    for i in range(num_perms): 
     # Generate the ith permutation. 
     perm = [] 
     remainder = i 

     # Clone the list so we can remove items from it as we 
     # add them to our permutation. 
     items = lst[:] 

     # Pick out each item in turn. 
     for j in range(len(lst) - 1): 
      # Divide the remainder at the previous step by the 
      # next factorial down, to get the item number. 
      divisor = factorial(len(lst) - j - 1) 
      item_num = remainder/divisor 

      # Add the item to the permutation, and remove it 
      # from the list of available items. 
      perm.append(items[item_num]) 
      items.remove(items[item_num]) 

      # Take the remainder for the next step. 
      remainder = remainder % divisor 

     # Only one item left - add it to the permutation. 
     perm.append(items[0]) 

     # Add the permutation to the list. 
     all_perms.append(perm) 

    return all_perms