Algorithme de Heap en Python
Bonjour à tous,
Je vous sollicite car j'essaie éperdument de faire marcher un algorithme qui me permettrait d'avoir toutes les permutations et de les insérés dans une liste.
En clair en terme de pseudo code mon algorithme consiste à faire cela :
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| fin=[1,2,3]
resultat=[]
def echanger(liste, i, j):
liste[i], liste[j] = liste[j], liste[i]
#VERSION RECURSIVE QUI BEUG encore
def Permut(liste, n):
if n==1 :
return liste
else :
for i in range (1,n):
Permut(liste,n-1)
if n%2==0 :
echanger(liste,i,n-1)
resultat.append(list(liste))
else:
echanger(liste, 0,n-1)
resultat.append(list(liste)) |
Le pseudo-code est simplement : (J'essaye d'implémenter l'algorithme de permutation de Heap)
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| Permutation (Entier : n, Liste A):
Si n = 1 alors
Retourner la liste Agorithme
Sinon
Pour i allant de 0 à n-1
Permuter(n-1,A)
Si n est pair alors :Permut(fin,3)
resultat
=> [[1, 2, 3], [3, 2, 1], [3, 2, 1], [1, 2, 3]]
echanger(A[i],A[n-1])
Sinon
echanger(A[0],A[n-1])
Fin Si
Fin For
Permuter(n-1,A);
Fin Si |
En clair j'ai essayé de le faire avec des listes en variables globales mais par exemple quand je tape : Permut(fin,3) avec 3 pour donner la taille de la liste :
Code:
1
2
3
| Permut(fin,3)
resultat
=> [[1, 2, 3], [3, 2, 1], [3, 2, 1], [1, 2, 3]] |
SI vous avez une solution, ou plutôt une piste ça serait vraiment cool ! Merci d'avance.
