Создать все перестановки в списке в лексико-порядке

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 

Это мой главный вопрос; однако при запуске этой программы все еще отсутствуют элементы. Это не совсем работает, поэтому, если вы видите место, где что-то явно не так, не стесняйтесь сказать мне, что определенная линия - это то, что вызывает мои проблемы. Если это помогает, это основано на этом идентичной (и правильно) версии, написанной в 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 
) 

Так это то, что мой код Python должен делать; Я просто не могу заставить его сделать это пока. Спасибо за любое ваше время и усилия.

Answer 1

Похоже, вы столкнулись с проблемой, потому что вы не скопировали x достаточно скоро, и поэтому вы иногда изменяете x после того, как он был добавлен в permList. Это может быть решена путем добавления 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]] 

Чуть более «вещий» версия может выглядеть следующим образом:

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 показывает, что они производят одинаковые ответы, поэтому похоже, что ваш алгоритм был правильным, за исключением этой небольшой ошибки.