Algorithme permutation - C - Programmation
Marsh Posté le 08-03-2008 à 12:19:27
Voici une autre définition que je vous fait partager:
une permutation d'un ensemble E:
c'est un n-upplet qui commence par x1 suivi d'une permutation de E privé de x1
ou un n-upplet qui commence par x2 suivi d'une permutation de E privé de x2
ou un n-upplet qui commence par x3 suivi d'une permutation de E privé de x3
...
ou un n-upplet qui commence par xn suivi d'une permutation de E privé de xn
où x1, x2, x3 .... xn sont les éléments de E
Marsh Posté le 11-03-2008 à 15:19:54
Bonjour,
Pas besoin de récursion pour faire ce travail...
L'idée est de gérer un tableau contenant les indices des éléments pris dans les listes successives. Le premier indice indique l'élément à prendre parmi N : il varie de 0 à N-1. Le deuxième de 0 à N-2, etc. jusqu'au dernier qui reste toujours nul. C'est comme un nombre à plusieurs chiffres où chaque chiffre compte selon une base variable selon le rang du-dit chiffre. Astuce : faire une boucle descendante pour que l'indice de boucle corresponde avec la "base" de chaque indice dans le tableau, c'est-à-dire le nombre d'éléments qui, s'il est atteint, permet de mettre cet indice à zéro et incrémenter le suivant.
Pour déterminer chaque permutation, il est difficile de prendre une chaîne de caractères et de la découper pour éliminer l'élément pris à chaque fois. Le truc est de décaler les éléments restants à droite de celui qui a été pris d'une position vers la gauche.
Si tu possèdes une calculette programmable, commence par faire des essais dessus pour comprendre le système.
Compris ? Vu la politique de la maison, personne n'écrira ton code à ta place...
Bon courage.
Marsh Posté le 11-03-2008 à 18:58:11
en C++ il y a std::next_permutation
oui je sais ici c'est du C, je signale juste qu'en C++ c'est déjà dans la STL.
Qd je faisais mes études, mon prof de C tolérait qu'on mette du C++ tant qu'on fournissait l'interface en C correspondante.
exemple :
Code :
|
Au cas où ça serait un exercice avec un prof aussi tolérant...
Marsh Posté le 08-03-2008 à 12:02:34
Salut à tous,
J'essaie de trouver un algorithme claire pour pouvoir écrire de manière facile l'algorithme des permutations dons je rappelle brièvement le principe avec un exemple:
Soit un tableau T={1,2,3} (je prend ici 3 valeurs, j'aurai pu en prendre N)
permutation (T);
123
132
213
231
312
321
Je précise que j'ai déjà trouvé des fonctions en C qui me permettent cela, je ne les comprend pas complètement, en voici un exemple:
J'ai trouvé également un algorithme que j'ai essayer d'implementer dont je ne saisis complètement pas la ligne en rouge:
fonction permut (tableau) /* ou un pointeur */
foreach a in tableau do
print a
sous_tableau=tableau - element_a
if sous_tableau=1case /* test de fin de recurtion */
then print sous_tableau[0]+cr/lf
else permut(sous_tableau) /* recurtion */
end if
end for
end fonction
Voici mon essai d'implémentation en C:
L'exécution donne le résultat inattendu suivant:
1 2 3
3 2
2 1 3
3 1
3 1 2
2 1
Si vous pensez détenir un meilleure algorithme dans le sens plus claire a la compréhension, et plus facile à implémenter, ou tous simplement si vous voyez des erreur dans cet algorithme ou dans mon implémentation, n'hésitez pas à m'en faire part, je vous serez trés reconnaissant !
Merci d'avance pour toutes votre aide !