Discussion :

[Haaggen]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[Flodelarab]

Bonjour

La quantité d'ordre de n objets est n! (factorielle) !
Il ne faut pas que tu permutes beaucoup d'objets si tu veux que ton ordi suive

Pourquoi ton "i" va de 1 à n-1 au lieu de 0 à n-1 ?

[disedorgue]

Bonjour,

Si c'est en python, pourquoi réinventer la roue ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
>>> import itertools
>>> list(itertools.permutations([1, 2, 3]))
[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]

Et en consultant la doc, tu peux voir d'autres approches de l'algo...