Forum |  HardWare.fr | News | Articles | PC | S'identifier | S'inscrire | Shop Recherche
1680 connectés 

  FORUM HardWare.fr
  Programmation
  Algo

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

 
 


 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

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

n°1008711
slvn
Posté le 10-03-2005 à 19:01:38  profilanswer
 

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

mood
Publicité
Posté le 10-03-2005 à 19:01:38  profilanswer
 

n°1009039
dark86
Posté le 10-03-2005 à 23:53:55  profilanswer
 

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

n°1009167
slvn
Posté le 11-03-2005 à 00:46:45  profilanswer
 

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  

n°1009178
art_dupond
je suis neuneu... oui oui !!
Posté le 11-03-2005 à 00:59:04  profilanswer
 

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
n°1009202
slvn
Posté le 11-03-2005 à 02:53:33  profilanswer
 

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

n°1009224
darkoli
Le Petit Dinosaure Bleu
Posté le 11-03-2005 à 08:40:19  profilanswer
 

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
n°1009281
art_dupond
je suis neuneu... oui oui !!
Posté le 11-03-2005 à 09:58:50  profilanswer
 

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
n°1009438
slvn
Posté le 11-03-2005 à 11:14:29  profilanswer
 

:)
 
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..)

n°1009925
art_dupond
je suis neuneu... oui oui !!
Posté le 11-03-2005 à 15:28:37  profilanswer
 

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
n°1009926
Taz
bisounours-codeur
Posté le 11-03-2005 à 15:29:08  profilanswer
 

Recherche :o

mood
Publicité
Posté le 11-03-2005 à 15:29:08  profilanswer
 

n°1010897
leneuf22
Posté le 12-03-2005 à 19:35:56  profilanswer
 

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

n°1010921
leneuf22
Posté le 12-03-2005 à 20:29:54  profilanswer
 

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
n°1011032
Chronoklaz​m
Posté le 13-03-2005 à 00:11:56  profilanswer
 

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 !
n°1011071
slvn
Posté le 13-03-2005 à 01:52:45  profilanswer
 

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  
 

n°1011110
leneuf22
Posté le 13-03-2005 à 09:37:25  profilanswer
 

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
n°1011115
leneuf22
Posté le 13-03-2005 à 09:51:32  profilanswer
 

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
n°1011140
Chronoklaz​m
Posté le 13-03-2005 à 12:06:04  profilanswer
 

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 !
n°1011205
slvn
Posté le 13-03-2005 à 14:45:04  profilanswer
 


>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

n°1011260
leneuf22
Posté le 13-03-2005 à 16:29:50  profilanswer
 

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 :-) )

n°1011262
fra0
Posté le 13-03-2005 à 16:32:39  profilanswer
 

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
n°1011265
Chronoklaz​m
Posté le 13-03-2005 à 16:37:24  profilanswer
 

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


---------------
Scheme is a programmable programming language ! I heard it through the grapevine !
n°1011266
leneuf22
Posté le 13-03-2005 à 16:41:50  profilanswer
 

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

n°1011268
Chronoklaz​m
Posté le 13-03-2005 à 16:44:23  profilanswer
 

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


---------------
Scheme is a programmable programming language ! I heard it through the grapevine !
n°1011270
fra0
Posté le 13-03-2005 à 16:50:04  profilanswer
 

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

n°1011278
leneuf22
Posté le 13-03-2005 à 16:57:55  profilanswer
 

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

n°1011284
fra0
Posté le 13-03-2005 à 17:07:54  profilanswer
 

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

n°1011286
leneuf22
Posté le 13-03-2005 à 17:11:52  profilanswer
 

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
n°1011303
fra0
Posté le 13-03-2005 à 17:26:52  profilanswer
 

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

n°1011321
leneuf22
Posté le 13-03-2005 à 17:36:29  profilanswer
 

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.

n°1011358
slvn
Posté le 13-03-2005 à 17:53:50  profilanswer
 

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.

n°1011368
dark86
Posté le 13-03-2005 à 18:19:41  profilanswer
 

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
n°1011474
fra0
Posté le 13-03-2005 à 20:11:20  profilanswer
 

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. }

n°1011485
leneuf22
Posté le 13-03-2005 à 20:33:59  profilanswer
 

: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
n°1011490
dark86
Posté le 13-03-2005 à 20:42:06  profilanswer
 

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

n°1011678
fra0
Posté le 14-03-2005 à 01:31:36  profilanswer
 

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.
 

mood
Publicité
Posté le   profilanswer
 


Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  Algo

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

 

Sujets relatifs
Algo de dijkstra pour un mappy[Algo][Java] Optimiser la répartition d'un algo
MySQL requête ciblée sur une chaine de caractèreComment Charger une chaine (venant d'un formulaire) dans un tableau ?
vba: récup chaine de carac[C++/SQL./Oracle] Juste un petit problème de chaine...
taritement chaîne de caractères sous access[RECHERCHE] Algo de Tri en C
Réutilisation d'une chaine de caractére !!Chaîne de caractères - Obtenir la longueur en points
Plus de sujets relatifs à : [algo] toutes les permutations d'une chaine de charatere

Forum MesDiscussions.Net, Version 2010.2
(c) 2000-2011 Doctissimo
Page générée en 0.130 secondes

Copyright © 1997-2022 Hardware.fr SARL (Signaler un contenu illicite / Données personnelles) / Groupe LDLC / Shop HFR