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>
  5. void print(const int *v, const int size)
  6. {
  7.   if (v != 0) {
  8.     for (int i = 0; i < size; i++) {
  9.       printf("%4d", v[i] );
  10.     }
  11.     printf("\n" );
  12.   }
  13. } // print
  16. void permutation(int *Value, int N, int k)
  17. {
  18.   static int level = -1;
  19.   level = level+1;
  20.   Value[k] = level;
  22.   if (level == N)
  23.     print(Value, N);
  24.   else
  25.     for (int i = 0; i < N; i++)
  26.       if (Value[i] == 0)
  27.         permutation(Value, N, i);
  29.   level = level-1;
  30.   Value[k] = 0;
  31. }
  34. int main()
  35. {
  36.   const int N = 4;
  37.   int Value[N];
  39.   for (int i = 0; i < N; i++) {
  40.     Value[i] = 0;
  41.   }
  43.   permutation(Value, N, 0);
  45.   return EXIT_SUCCESS;
  46. }


 
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>
  5. int array[3]={1,2,3};
  8. int* sousTableau(int indice, int * tableau, int N){
  9.   int curseur=0;
  10.   int *sous_tableau=malloc( (N-1)*sizeof(*sous_tableau) );
  11.   assert(sous_tableau);
  13.   for(int i=0; i<N; i++)
  14.     if( i != indice ){
  15.       sous_tableau[curseur]=tableau[i];
  16.       curseur++;
  17.     }
  18.   return sous_tableau;
  19. }
  21. void permutation(int * tableau, int N){
  22.   int * sous_tableau=NULL;
  24.   for(int i=0; i < N; i++)
  25.     {
  26.       printf("%d ",tableau[i]);
  27.       sous_tableau=sousTableau(i,tableau,N);
  28.       if( N == 2){
  29. printf("%d ",sous_tableau[0]);
  30. printf("\n" );
  31.       }
  32.       else
  33. permutation(sous_tableau, N-1);
  34.    }
  36. }
  38. int main(void){
  39.   permutation(array,3);
  40.   return EXIT_SUCCESS;
  41. }


 
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