Algorithme permutation

Algorithme permutation - C - Programmation

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:

Code :
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. void print(const int *v, const int size)
  4. {
  5.   if (v != 0) {
  6.     for (int i = 0; i < size; i++) {
  7.       printf("%4d", v[i] );
  8.     }
  9.     printf("\n" );
  10.   }
  11. } // print
  12. void permutation(int *Value, int N, int k)
  13. {
  14.   static int level = -1;
  15.   level = level+1;
  16.   Value[k] = level;
  17.   if (level == N)
  18.     print(Value, N);
  19.   else
  20.     for (int i = 0; i < N; i++)
  21.       if (Value[i] == 0)
  22.         permutation(Value, N, i);
  23.   level = level-1;
  24.   Value[k] = 0;
  25. }
  26. int main()
  27. {
  28.   const int N = 4;
  29.   int Value[N];
  30.   for (int i = 0; i < N; i++) {
  31.     Value[i] = 0;
  32.   }
  33.   permutation(Value, N, 0);
  34.   return EXIT_SUCCESS;
  35. }


 
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:

Code :
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <assert.h>
  4. int array[3]={1,2,3};
  5. int* sousTableau(int indice, int * tableau, int N){
  6.   int curseur=0;
  7.   int *sous_tableau=malloc( (N-1)*sizeof(*sous_tableau) );
  8.   assert(sous_tableau);
  9.   for(int i=0; i<N; i++)
  10.     if( i != indice ){
  11.       sous_tableau[curseur]=tableau[i];
  12.       curseur++;
  13.     }
  14.   return sous_tableau;
  15. }
  16. void permutation(int * tableau, int N){
  17.   int * sous_tableau=NULL;
  18.   for(int i=0; i < N; i++)
  19.     {
  20.       printf("%d ",tableau[i]);
  21.       sous_tableau=sousTableau(i,tableau,N);
  22.       if( N == 2){
  23. printf("%d ",sous_tableau[0]);
  24. printf("\n" );
  25.       }
  26.       else
  27. permutation(sous_tableau, N-1);
  28.    }
  29. }
  30. int main(void){
  31.   permutation(array,3);
  32.   return EXIT_SUCCESS;
  33. }


 
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 !  :jap:  
 

Reply

Marsh Posté le 08-03-2008 à 12:02:34   

Reply

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

Reply

Marsh Posté le 08-03-2008 à 14:35:16    

Pas d'idée ?

Reply

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.


Message édité par jxano le 11-03-2008 à 15:26:57

---------------
Honorez les cons : c'est ainsi qu'ils nous fichent la paix.
Reply

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 :
  1. extern "C" void permutation( int T[], int size )
  2. {
  3.    std::sort( T, T + size );
  4.    do
  5.    {
  6.        print( T, size ); /* je reprends ta fonction */
  7.    }
  8.    while( std::next_permutation( T, T + size ) );
  9. }


 
Au cas où ça serait un exercice avec un prof aussi tolérant... ;)

Reply

Marsh Posté le 11-03-2008 à 19:39:36    

au pire il zieutes dans le source de next_permutation ;)

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed