permutations Python récursive

Question

J'essaie de résoudre un problème en utilisant backtracking et j'ai besoin des permutations de nombres pour cela. J'ai cet algorithme de base qui le fait mais le problème est ... les résultats ne viennent pas dans l'ordre normal.

def perm(a,k=0): 
    if(k==len(a)): 
     print(a) 
    else: 
     for i in range(k,len(a)): 
     a[k],a[i] = a[i],a[k] 
     perm(a, k+1) 
     a[k],a[i] = a[i],a[k] 

Exemple: pour [1,2,3] les résultats normaux seraient: [1,2,3] [1,3,2] [2,1,3] [2,3,1 ] [3,1,2] [3,2,1]

Considérant que cet algorithme va échanger les 2 derniers éléments. Je comprends pourquoi. Je ne sais pas comment corriger cela.

Je ne veux pas utiliser les permutations d'itertools. Le code ci-dessus peut-il être facilement réparé pour fonctionner correctement? Quelle serait la complexité de cet algorithme d'en haut?

Answer 1

est ici un (suboptimale, parce que les listes copier tout le temps) solution:

def perm(a, prev=[]): 
    if not a: 
     print(prev) 
    for index, element in enumerate(a): 
     perm(a[:index] + a[index+1:], prev + [element]) 

L'ordre il est imprimé:

>>> perm([1,2,3]) 
[1, 2, 3] 
[1, 3, 2] 
[2, 1, 3] 
[2, 3, 1] 
[3, 1, 2] 
[3, 2, 1] 

Answer 2

Une fonction de générateur récursif qui donne des permutations dans l'ordre attendu en ce qui concerne la liste originale:

def perm(a): 
    if len(a) <= 1: 
     yield a 
    else: 
     for i in xrange(len(a)): 
      for p in perm(a[:i]+a[i+1:]): 
       yield [a[i]]+p 

a = [1, 2, 3] 

for p in perm(a): 
    print(p) 

[1, 2, 3] 
[1, 3, 2] 
[2, 1, 3] 
[2, 3, 1] 
[3, 1, 2] 
[3, 2, 1]