1

I am very much a beginner. I am trying to write a program that, given the number of elements (1-9) in the list as a parameter, will then output all permutations of the list in lexicographical order. In the program it is adding on each permutation as a list into a larger list that contains all the permutations in order. Although the program is not working as expected in general, one main problem I'm having is with this while loop In line 10, I want the list to stop compiling once the final permutation has been added to the list. For example, if my input parameter is n = 4, the last permutation/element should be [4,3,2,1]. However, when I run this program, that element is in the list three times at the end. I don't know how this is so when it should terminate that while loop once it has been added.

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

That is my main question; however, this program is still missing elements when I run it. It isn't quite working, so if you see a spot where something is obviously wrong, feel free to tell me that particular line is what is causing my problems. If it helps, this is based on this identical (and correct) version written in Mathematica 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
)

So this is what my Python code should be doing; I just can't get it to do so just yet. Thanks for any of your time and effort.

4

1 回答 1

0

看起来您遇到了问题，因为您没有x足够快地复制，因此您有时会x在将其添加到permList. 这可以通过x = x[:]在 while 循环的开头添加来解决：

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]]

一个稍微“pythonic”的版本可能看起来像：

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

于 2013-04-29T06:09:23.770 回答