以字典順序生成列表的所有排列

Question

我非常喜歡初學者。我試圖編寫一個程序，該列表以列表中元素（1-9）的數量作爲參數，然後將按字典順序輸出列表的所有排列。在程序中，它將每個排列作爲一個列表添加到一個更大的列表中，該列表按順序包含所有排列。雖然程序一般情況下並不像預期的那樣工作，但我遇到的一個主要問題是使用while循環在第10行中，我希望列表在最終的排列被添加到列表中時停止編譯。例如，如果我的輸入參數是n = 4，則最後一個排列/元素應該是[4,3,2,1]。但是，當我運行這個程序時，該元素最後會在列表中出現三次。我不知道這是什麼時候它應該終止while循環，一旦它被添加。

def ourPermutations(n): 
    x=list(range(1,n+1)) 
    permList = [] 
    permList+=[x] 

    xcopy = x[:] 
    finalPerm = xcopy[::-1] 


    while x != finalPerm: 
     istar = n-2 
     while x[istar] > x[istar+1]: 
      istar -= 1 
     jstar = n-1 
     while x[jstar] < x[istar]: 
      jstar -= 1 
     x[istar],x[jstar] = x[jstar],x[istar] 
     if istar+1 == n-1: 
      x = x[:] 
     else: 
      a = x[istar+1:] 
      a = a[::-1] 
      x = x[:istar+1] + a 
     permList += [x] 

    return permList 

這是我的主要問題;然而，當我運行它時，這個程序仍然缺少元素。它不是很有效，所以如果你看到某個地方出現明顯錯誤的地方，請隨時告訴我特定線路是什麼導致了我的問題。如果有幫助，這是基於在寫數學8此相同的（正確）版本：

ourpermutations[n_] := (
    ourlist = {x=Range[1,n]}; 
    While[ 
     x != Reverse[Range[1,n]], 
     istar = n-1; 
     While[x[[istar]] > x[[istar+1, istar--]; 
     jstar = n; While[x[[jstar]] < x[[istar]], jstar--]; 
     x[[{istar, jstar}]] = x[[{jstar, istar}]]; 
     AppendTo[ourlist, x = Join[Take[x,istar], Reverse[Drop[x,istar]]]] 
    ]; 
    ourlist 
) 

所以這是我的Python代碼應該做的事;我現在還無法做到這一點。感謝您的時間和精力。

Answer 1

看起來您正遇到問題，因爲您沒有及時複製x，因此您有時在將其添加到permList後修改了x。這可以通過在while循環開始加入x = x[:]解決：

def ourPermutations(n): 
    x=list(range(1,n+1)) 
    permList = [] 
    permList+=[x] 

    xcopy = x[:] 
    finalPerm = xcopy[::-1] 

    while x != finalPerm: 
     x = x[:] 
     istar = n-2 
     while x[istar] > x[istar+1]: 
      istar -= 1 
     jstar = n-1 
     while x[jstar] < x[istar]: 
      jstar -= 1 
     x[istar],x[jstar] = x[jstar],x[istar] 
     if istar+1 == n-1: 
      x = x[:] 
     else: 
      a = x[istar+1:] 
      a = a[::-1] 
      x = x[:istar+1] + a 
     permList += [x] 

    return permList 

>>> ourPermutations(3) 
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]] 
>>> ourPermutations(4) 
[[1, 2, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4], [1, 3, 4, 2], [1, 4, 2, 3], [1, 4, 3, 2], [2, 1, 3, 4], [2, 1, 4, 3], [2, 3, 1, 4], [2, 3, 4, 1], [2, 4, 1, 3], [2, 4, 3, 1], [3, 1, 2, 4], [3, 1, 4, 2], [3, 2, 1, 4], [3, 2, 4, 1], [3, 4, 1, 2], [3, 4, 2, 1], [ 
4, 1, 2, 3], [4, 1, 3, 2], [4, 2, 1, 3], [4, 2, 3, 1], [4, 3, 1, 2], [4, 3, 2, 1]] 

稍微更「Python化」的版本可能看起來像：

def our_permutations(n): 
    x = list(range(1, n+1)) 
    perm_list = [x] 
    final_perm = x[::-1] 

    while x != final_perm: 
     x = x[:] 
     istar = n-2 
     while x[istar] > x[istar+1]: 
      istar -= 1 
     jstar = n-1 
     while x[jstar] < x[istar]: 
      jstar -= 1 
     x[istar],x[jstar] = x[jstar],x[istar] 
     if istar+1 != n-1: 
      a = x[istar+1:] 
      a = a[::-1] 
      x = x[:istar+1] + a 
     perm_list += [x] 

    return perm_list 

檢查，對itertools.permutation這些功能表明，它們產生的相同的答案，所以它看起來像你的算法是正確的，除了那個小錯誤。