[algo] toutes les permutations d'une chaine de charatere

toutes les permutations d'une chaine de charatere [algo] - Algo - Programmation

Marsh Posté le 10-03-2005 à 19:01:38    

Bonjour,
 
 
Est-ce que vous connaissez un algo simple, non récursif, pour afficher toutes les permutations d'une chaine de charatere.
 
Sylvain

Reply

Marsh Posté le 10-03-2005 à 19:01:38   

Reply

Marsh Posté le 10-03-2005 à 23:53:55    

(flag)
A premiere vue je ne crois pas avoir deja vu d'algo non récursif explorant n! possibilités.....

Reply

Marsh Posté le 11-03-2005 à 00:46:45    

bon je viens de pondre une idée, par contre ca me saoul a implementer :d  (quoi que peut etre on verra)
 
pour une chaine de N char.
il faut faire parcourrir i de 1 a N!
decomposer i en:  
a1*(n-1)! + a2*(n-2)! + ... + an
 
et puis les (a)n peuvent faire une bijection des characteres de la chaine :D  

Reply

Marsh Posté le 11-03-2005 à 00:59:04    

simple mais pas non récursif (edit: et meme pas juste d'ailleurs :ange: )
 

faire autant de fois que de lettres
   inverser premiere et derniere lettre (avec le dernier mot obtenu)
   inverser deuxieme et derniere lettre (avec le dernier mot obtenu)
   ...


Message édité par art_dupond le 11-03-2005 à 10:01:41

---------------
oui oui
Reply

Marsh Posté le 11-03-2005 à 02:53:33    

ayé ca marche en non reccursif :)
 
>art_dupond:  
autant de fois qu'il y a de lettres :??: comment on arrive a n! alors??

Reply

Marsh Posté le 11-03-2005 à 08:40:19    

slvn a écrit :

bon je viens de pondre une idée, par contre ca me saoul a implementer :d  (quoi que peut etre on verra)
 
pour une chaine de N char.
il faut faire parcourrir i de 1 a N!
decomposer i en:  
a1*(n-1)! + a2*(n-2)! + ... + an
 
et puis les (a)n peuvent faire une bijection des characteres de la chaine :D

Ouais, c'est cette méthode que j'ai utilisée (pour un autre problème).
En revanche il faut faire attention au type que tu utilises pour tes entiers car 12 ! = 479 001 600 mais 13! = 6 227 020 800.


Message édité par darkoli le 11-03-2005 à 08:40:39

---------------
Le site de l'année :D (XHTML 1.0 strict) : http://darkoli.free.fr/index.html
Reply

Marsh Posté le 11-03-2005 à 09:58:50    

slvn a écrit :

ayé ca marche en non reccursif :)
 
>art_dupond:  
autant de fois qu'il y a de lettres :??: comment on arrive a n! alors??


j'ai pas compris. Pourquoi je dois arriver à n! ?
 
 
ah ok j'ai compris...
 
euh... 2 sec :p
 
 
re-edit: bon je ne trouve plus comment ca marchait. Là c'est sûr que c'est pas bon :p


Message édité par art_dupond le 11-03-2005 à 10:01:21

---------------
oui oui
Reply

Marsh Posté le 11-03-2005 à 11:14:29    

:)
 
Sinon de manière recursive, est-ce que y a moyen simple comme tu le dis art_dupond ??
(ie, sans passer par une arbre ou il y aurait n choix au level 1, n-1 choix au level 2, etc..)

Reply

Marsh Posté le 11-03-2005 à 15:28:37    

il y a une méthode avec des permutations (un peu comme j'ai fait), mais je n'arrive plus à la retrouver dans le fouilli de sacs noeuds dans ma tête...
 
je cherche...


---------------
oui oui
Reply

Marsh Posté le 11-03-2005 à 15:29:08    

Recherche :o

Reply

Marsh Posté le 11-03-2005 à 15:29:08   

Reply

Marsh Posté le 12-03-2005 à 19:35:56    

J'ai fait ce que tu cherches en itératif, je vais le chercher dans mon bordel...

Reply

Marsh Posté le 12-03-2005 à 20:29:54    

Ouf, c'est bon
bon, le truc est en C mais l'algo est court et pas compliqué (c'est juste la boucle de 20 lignes qui est intéressante) :
 

Code :
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <stdlib.h>
  5. void permute(char* const);
  7. int main(void) {
  8. char s[24];
  9. size_t fin;
  11. puts("Entrer les lettres :" );
  12. fgets(s, sizeof s, stdin);
  14. fin = strlen(s)-1;
  16. if(s[fin] == '\n')
  17.  s[fin] = '\0';
  18. if(s[0] == '\0')
  19.  return 0;
  21. permute(s);
  23. return 0;
  24. }
  27. void permute(char* const s) {
  28. char
  29.  c,
  30.  *pRotation;
  31. const unsigned
  32.  longueurchaine = strlen(s),
  33.  maxcurseur = longueurchaine-1;
  34. unsigned
  35.  *boucle = calloc(longueurchaine, sizeof *boucle);
  36. size_t
  37.  curseur=0;
  38. FILE
  39.  *fSortie = fopen("bidule.txt", "w" );
  42. if(fSortie == NULL) {
  43.  if(boucle == NULL)
  44.   return;
  45.  free(boucle);
  46.  return;
  47. }
  48. if(boucle == NULL) {
  49.  fclose(fSortie);
  50.  return;
  51. }
  53. boucle[0] = longueurchaine;
  56. /* c'est cette boucle qui est interessante :*/
  57. while(boucle[0]) {
  58.  if(boucle[curseur]) {
  59.   while(curseur < maxcurseur) {
  60.    ++curseur;
  61.    boucle[curseur] = longueurchaine-curseur;
  62.   }
  63.   fputs(s, fSortie);
  64.   fputc('\n', fSortie);
  65.  }
  66.  else {
  67.   --curseur;
  68.   pRotation = s+curseur;
  69.   c = *pRotation;
  70.   while(*pRotation = pRotation[1])
  71.    ++pRotation;
  72.   *pRotation = c;
  73.  }
  74.  --boucle[curseur];
  75. }
  77. free(boucle);
  78. fclose(fSortie);
  79. }


 
PS : évidemment, si il y a des répétitions dans la chaîne de caractères, j'ai pas trouvé mieux que de tout classer par ordre alphabétique (ou faire un arbre à la limite) pour virer les doublons


Message édité par leneuf22 le 13-03-2005 à 17:12:36
Reply

Marsh Posté le 13-03-2005 à 00:11:56    

Et recursif à l'ordre superieur ?  :pt1cable:  
 
Mais avec les repetitions  :whistle:  
 

Citation :


 
(define (mapcan f L)
  (if (null? L)
      '()
      (append! (f (car L))
               (mapcan f (cdr L)))))
 
(define (words n L)
  (if (= n 0)
      '(())
      (let ((res (words (- n 1) L)))
        (mapcan (lambda (w)  
                  (map (lambda (sym) (cons sym w))
                       L))
                res))))
 
(let ((ma-liste (string->list "abc" )))
    (words (length ma-liste) ma-liste))  
 
Ca donne :
 
((#\a #\a #\a)
 (#\b #\a #\a)
 (#\c #\a #\a)
 (#\a #\b #\a)
 (#\b #\b #\a)
 (#\c #\b #\a)
 (#\a #\c #\a)
 (#\b #\c #\a)
 (#\c #\c #\a)
 (#\a #\a #\b)
 (#\b #\a #\b)
 (#\c #\a #\b)
 (#\a #\b #\b)
 (#\b #\b #\b)
 (#\c #\b #\b)
 (#\a #\c #\b)
 (#\b #\c #\b)
 (#\c #\c #\b)
 (#\a #\a #\c)
 (#\b #\a #\c)
 (#\c #\a #\c)
 (#\a #\b #\c)
 (#\b #\b #\c)
 (#\c #\b #\c)
 (#\a #\c #\c)
 (#\b #\c #\c)
 (#\c #\c #\c))
 


 
Quelqu'un est chaud pour l'ecrire en ML ou Haskell ? :D ... avec les Monads ?  :pt1cable:  


Message édité par Chronoklazm le 13-03-2005 à 00:26:22

---------------
Scheme is a programmable programming language ! I heard it through the grapevine !
Reply

Marsh Posté le 13-03-2005 à 01:52:45    

oulala je capte rien ni au premier ni au deuxieme :/
(pt etre que je suis pas en etat la :D)
 
>leneuf22
pour l'iteratif, en fait je l'ai deja fait. Mais le mien est beaucoup plus long :/
tu peux expliquer un peu ta boucle :)
 
 
>Chronoklaz
euh c'est quoi le langage la :??: j'ai l'impression que la police de caractere passe mal chez moi  
 

Reply

Marsh Posté le 13-03-2005 à 09:37:25    

OK, je vais tenter de t'expliquer :
 
Déjà, si le nombre de lettres était fixé, par exemple 5 lettres, l'algo pourrait se traduire en 5 boucles for imbriquées, ça aurait été beaucoup plus facile.
 
Or ici, le nombre de lettres n'est pas fixé, il faut donc s'adapter :
boucle comme son nom l'indique, joue le role d'un tableau de boucles for.
Ce code fait donc exactement l'effet de x boucles for imbriquées, au détail près que l'on ne connait pas x.
(boucle contient un nombre d'éléments égal nombre de lettres entrées)
 
Ensuite, pour générer toutes les permutations possibles, j'avais trouvé que de simples rotations suffisaient :
Pour que tu comprennes mieux, si on avait nos x boucles for imbriquées, il faudrait faire une rotation des n+1 derniers caractères à chaque fois que l'on sort de la boucle n (j'appelle la boucle la plus globale la boucle x, et la moins globale la boucle 1 : au sortir de la boucle 1 (qui n'est pas vraiment une boucle puisqu'elle ne se répète qu'une seule fois), on fait une rotation des 2 derniers caractères. Le sens importe peu, il faut juste que ça soit le même à chaque fois). Ce système de rotations suffit à obtenir toutes les permutations.
 
Ensuite, tu auras remarqué que le tableau "boucle" contient des valeurs. En fait, il contient pour chaque boucle le compteur de celle-ci. La première boucle (boucle[0]) est initialisée une seule fois au nombre de caractères x, et les autres seront initialisées à x-1, x-2... 1 : on retrouve bien x(x-1)(x-2)...(1) = x!. Il faut juste réinitialiser le compteur de chaque boucle quand on y entre.
 
 

Code :
  1. while(boucle[0]) { // tant que la boucle la plus globale n'est pas finie, il reste des permutations
  2.     if(boucle[curseur]) { //si la boucle courante n'est pas finie :
  3.         while(curseur < maxcurseur) { // tant qu'il y a des boucles plus locales, on y entre
  4.             ++curseur; // donc +1 au curseur de boucles
  5.             boucle[curseur] = longueurchaine-curseur; // on réinitialise le compteur de la boucle
  6.         }
  7.         // ici on est dans la boucle la plus locale (ce n'est pas vraiment une boucle puisque exécutée une seule fois d'affilée)
  8.         fputs(s, fSortie); // on a donc une permutation de plus à inscrire
  9.         fputc('\n', fSortie);
  10.     }
  11.     else { // la boucle courante est finie
  12.         --curseur; // on revient a une boucle plus globale
  13.         pRotation = s+curseur; //et on fait une rotation des derniers caractères
  14.         c = *pRotation;
  15.         while(*pRotation = pRotation[1]) // attention, ceci est bien une affectation et non un test logique
  16.             ++pRotation;
  17.         *pRotation = c;
  18.     }
  19.     --boucle[curseur]; // on décrémente le compteur de la boucle courante
  20. }


 
 
EDIT (un peu tardif) : j'ai viré mes conneries


Message édité par leneuf22 le 13-03-2005 à 16:26:30
Reply

Marsh Posté le 13-03-2005 à 09:51:32    

Heu, sinon, Chronoklazm et moi on n'a pas compris le problème de la même façon apparemment...
 
Le code de Chronoklazm donne n^n réponses (toutes les combinaisons possibles, sans notion d'ordre), et le mien en donne n! (toutes les permutations possibles), ce n'est pas tout à fait pareil.


Message édité par leneuf22 le 13-03-2005 à 10:14:57
Reply

Marsh Posté le 13-03-2005 à 12:06:04    

Arf, avais trop bu moi ! Mais la fonction words me plait bien :)
 

Citation :


 
(define (permutations L)
  (if (null? L)
      '(())
      (map-append
       (lambda (x)
  (map (lambda (reste) (cons x reste))
       (permutations (remove x L))))
       L)))
 
(permutations (string->list "abc" ))
 
Ca donne :
 
((#\a #\b #\c)  
 (#\a #\c #\b)  
 (#\b #\a #\c)  
 (#\b #\c #\a)
 (#\c #\a #\b)
 (#\c #\b #\a))
 
O(n!) en temps et en espace.
 


 
PS: slvn => C'est un dialecte de Lisp.


Message édité par Chronoklazm le 13-03-2005 à 12:09:57

---------------
Scheme is a programmable programming language ! I heard it through the grapevine !
Reply

Marsh Posté le 13-03-2005 à 14:45:04    


>leneuf22
oky j'ai capté l'aglo,  
solution très élégante :)  :jap:
 
>Chronoklazm
..bon pour le lisp, j'ai du mal avec la syntaxe :/ donc je laisse tomber
 
sylvain

Reply

Marsh Posté le 13-03-2005 à 16:29:50    

Content de t'avoir aidé
(je viens de me rendre compte que je pouvais faire mieux encore, j'ai édité mes posts plus haut : tu remarqueras qu'avec un while supplémentaire c'est encore plus élégant :-) )

Reply

Marsh Posté le 13-03-2005 à 16:32:39    

Code :
  1. #include <algorithm>
  2. using namespace std;
  4. void permute(char *src, unsigned n)
  5. {
  6.     sort(src,src+n);
  7.     do
  8.     {
  9.         cout<<src<<endl;
  10.     }
  11.     while(next_permutation(src,src+n));
  12. }


Message édité par fra0 le 13-03-2005 à 16:34:39
Reply

Marsh Posté le 13-03-2005 à 16:37:24    

Là on ne peut pas faire mieux que ca, je pense.


---------------
Scheme is a programmable programming language ! I heard it through the grapevine !
Reply

Marsh Posté le 13-03-2005 à 16:41:50    

En même temps on est dans le forum algo, donc utiliser ça, ça répond pas à la question...

Reply

Marsh Posté le 13-03-2005 à 16:44:23    

On va pas reinventer la roue c'est sur ... enfin qui sait :)


---------------
Scheme is a programmable programming language ! I heard it through the grapevine !
Reply

Marsh Posté le 13-03-2005 à 16:50:04    

leneuf...
 
#include <stdio.h>  
#include <string.h>  
#include <stdlib.h>  
 
!
 
 :sol:

Reply

Marsh Posté le 13-03-2005 à 16:57:55    

Et alors ? J'utilise le minimum qu'un système d'exploitation est sensé nous offrir (les E/S et la mémoire) : ce que j'ai fait est traduisible dans plein de langages, ton truc non, c'est complètement hors sujet.
On aurait été dans le forum C++ jveux bien, mais là faut pas pousser quand même

Reply

Marsh Posté le 13-03-2005 à 17:07:54    

:pt1cable:  
mouarf CodeGuard signale des dépassements d'accès sur ton code.

Reply

Marsh Posté le 13-03-2005 à 17:11:52    

Oups, 'me suis planté dans le calloc en effet, mettre longueurchaine à la place de maxcurseur
Ce genre de remarques est déjà plus constructif :-)
(j'ai édité)


Message édité par leneuf22 le 13-03-2005 à 17:12:55
Reply

Marsh Posté le 13-03-2005 à 17:26:52    

vi c'est mieux,
et quid des caractères multiples ?

Reply

Marsh Posté le 13-03-2005 à 17:36:29    

C'est ce que je disais plus haut, mon truc génère des doublons si il y a des caractères multiples.
Faut voir avec slvn si il veut prendre en compte ce cas, mais à part virer les doublons avec une recherche exhaustive, après la génération des résultats, je ne vois vraiment pas comment procéder.
 
Si il y a un "truc", ça m'intéresserait de le connaître, mais je pense que c'est déjà beaucoup plus complexe.

Reply

Marsh Posté le 13-03-2005 à 17:53:50    

meme si c'est pas ce que je souhaitais,  
j'aime bien la solution de fra0 :d
 
>a priori gerer toutes les permutations, ca voudrait dire enlever les doublons. avec ton algo c'est pas possible a gerer facilement.

Reply

Marsh Posté le 13-03-2005 à 18:19:41    

voila ce que j'ai fait, ca doit etre quasiment comme leneuf22, en tt cas c'est le meme principe , et ca gere pas non plus les doublons :(

Code :
  1. #include <string.h>
  2. #include <stdio.h>
  3. #include <malloc.h>
  5. int rot(char* mot, int n, int k)//fait une rotation des n-k derniers caracteres {
  6. char tmp=mot[k];
  7. if(k==n) return(0);
  8. for(int i=k;i<n-1;i++)
  9.  mot[i]=mot[i+1];
  10. mot[n-1]=tmp;
  11. return(0);
  12. }
  14. void main() {
  15. int cur,i,n,*nb;//cur:position actuelle ; nb=[n-1,n-2n...,0]:nb de boucles
  16. char s[30];//mot à traiter
  17. gets(s);
  18. n=strlen(s);
  19. nb=(int*) malloc(n*sizeof(int));
  20. for(i=0;i<n;i++) nb[i]=n-i-1;
  21. cur=n;
  23. while(cur!=-1)
  24.  if(nb[cur]!=0) {//reste t'il des rotations à faire?
  25.   for(i=cur+1;i<n;i++) nb[i]=n-i-1;
  26.   rot(s,n,cur);
  27.   nb[cur]--;
  28.   printf("%s\n",s);
  29.   cur=n-1;
  30.  }
  31.  else { //on remonte les '0' de 'nb'
  32.   rot(s,n,cur);
  33.   cur--;
  34.  }
  35.         free(nb);
  36. }


[edit];ajout de "free(nb);" ^^


Message édité par dark86 le 13-03-2005 à 21:00:23
Reply

Marsh Posté le 13-03-2005 à 20:11:20    

manque un free nan ?

Code :
  1. bool my_next_permutation(char *first, char *last)
  2. {
  3.     if (last-first<2) return false;
  5.     for(char *current,*i=last-1;current = i--;)
  6.     {
  7.         if (*i < *current)
  8.         {
  9.             char *maxi=last;
  10.             while (*i>=*--maxi);
  11.             iter_swap(i,maxi);
  12.             reverse(current,last);
  13.             return true;
  14.         }
  15.         if (i == first)
  16.         {
  17.             reverse(first, last);
  18.             return false;
  19.         }
  20.     }
  21. }

Reply

Marsh Posté le 13-03-2005 à 20:33:59    

:love:
Excellent, je mets ça de côté :jap:
 
Tu pourrais expliquer comment ton code marche ? Je ne comprends absolument la subtilité de cet algo ...
 
(sinon, pour le code de Dark86, ya pas que le free manquant qui va pas... enfin on est sur le forum algo alors on dira rien :) )


Message édité par leneuf22 le 13-03-2005 à 20:53:52
Reply

Marsh Posté le 13-03-2005 à 20:42:06    

lol, mouai, les free....
m'enfin il donne la liste voulue, c'est ce qu'on lui demande^^

Reply

Marsh Posté le 14-03-2005 à 01:31:36    

cf docs
 
à partir d'un mot,
ça revient à trouver le mot suivant dans l'ordre  lexicographique
qui utilise les mêmes lettres...
 
je suis sûr que tu peux résoudre ce problème.
 

Reply

Marsh Posté le    

Reply

Sujets relatifs:

Leave a Replay

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