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

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这些功能表明，它们产生的相同的答案，所以它看起来像你的算法是正确的，除了那个小错误。