Discussion :

[Didier77]

bonjour,
je cherche à faire une fonction qui genere tous les mots possibles
de 10 lettres en majuscule.
Petit problème, je n'arrive pas à trouver la ou les boucles pour generer ces mots...

[Thierry Chappuis]

L'énoncé générique du problème est de trouver comment générer toutes les permutations d'un ensemble fini d'éléments. Un fois l'algo posé sur papier, l'implantation en langage C devrait être aisée.

Thierry

[Didier77]

effectivement c'est bien ça le probleme

[Jean-Marc.Bourguet]

http://www.developpez.net/forums/sho...43&postcount=2

[millie]

Peut être devrais tu jetter un oeil à :

Generating all permutations: http://www-cs-faculty.stanford.edu/~knuth/fasc2b.ps.gz

[Didier77]

merci pour les liens je pense que je vais bien me prendre la tete lol

[Thierry Chappuis]

Voici une idée naïve d'algorithme. Si tu n'a pas de répétition de lettre et que tu désires générer toutes les permutations possibles:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
procedure PERMUTATIONS(chaine: chaine de caractères)
    tampon: chaine de caractères de longueur longueur(chaine)
    a <- 0
    b <- 1
    c <- 2
 
    tant que a < longeur(chaine) alors
        j <- 0
        echanger(0, a)
        tampon[j] <- chaine[0];
        incrémenter(a)
        incrémenter(j)
 
        tant que b < longueur(chaine) alors
            echanger(1, b)
            tampon[j] <- chaine[1];
            incrémenter(b)
            incrémenter(j)
 
            tant que c < longueur(chaine) alors
                echanger(2, c)
                tampon[j] <- chaine[2];
                incrémenter(c)
                incrémenter(j);
                ecrire_dans_fichier(tampon)
            ftant
        ftant
    ftant
fprocedure

Pour un mot de 10 lettres, tu obtiendras 10! = 3'628'800 permutations. Si tu as des répétitions de lettre, soit tu génères les doublons et tu les élimines par la suite, soit tu trouve un algo qui te permette de ne pas générer de doublon.

Je n'ai pas passé tellement de temps à vérifier la validité de l'algo...

Thierry

[Didier77]

C'est exactement ce que j'ai dit à mon chargé de tp et il a rigolé en me disant me donnerait une solution, j'ai hate de voir!
je donnerai la soluce

[acx01b]

salut

ton ennoncé c'était pour générer tous les mots en majuscule et pas pour générer les permutations ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
char mot[11] = "AAAAAAAAAA";
char *ptr = mot + 10;
while(1) {
  printf("%s\n",mot);
  char *ptr2 = ptr;
  while (*ptr2 == 'Z') {
    if (ptr2 == mot) goto fin;
    *ptr2-- = 'A';
  }
  (*ptr2)++;
}
fin:;

[droggo]

Koi,

C'est pas comme ça que je voyais le problème. J'avais compris que l'ensemble des 10 lettres de départ était déjà défini... Ca réguit considérablement la taille du problème.

Thierry

C'est bien comme ça que je prends le problème aussi, exercice tellement classique qu'on a dû le voir quelques centaines de fois, voire plus.

D'ailleurs,

L'énoncé générique du problème est de trouver comment générer toutes les permutations d'un ensemble fini d'éléments. Un fois l'algo posé sur papier, l'implantation en langage C devrait être aisée.

et

effectivement c'est bien ça le probleme

[souviron34]

salut

ton ennoncé c'était pour générer tous les mots en majuscule et pas pour générer les permutations ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
char mot[11] = "AAAAAAAAAA";
char *ptr = mot + 10;
while(1) {
  printf("%s\n",mot);
  char *ptr2 = ptr;
  while (*ptr2 == 'Z') {
    if (ptr2 == mot) goto fin;
    *ptr2-- = 'A';
  }
  (*ptr2)++;
}
fin:;

[millie]

Aaah, désolé, il y avait eu une discussion dans le forum Algo sur la génération de permutation et une autre dans le langage C, j'avais cru que c'était également sur les permutations, donc pour que tout le monde puisse écrire dans un seul sujet, j'ai tout mis dans algo.
Mais la génération de tous les mots de lettre en majuscule, c'est un problème de combinaison, dont la solution est donnée par le lien de Jean-Marc.

Il y a également un autre poste ici : http://www.developpez.net/forums/sho...d.php?t=228599

[alex_pi]

bonjour,
je cherche à faire une fonction qui genere tous les mots possibles
de 10 lettres en majuscule.
Petit problème, je n'arrive pas à trouver la ou les boucles pour generer ces mots...

J'espère qu'il ne te faut pas les stocker, parequ'il te faudrait quand même 1553 tera-octet :-) (en les séparants par un retour chariot)

salut

ton ennoncé c'était pour générer tous les mots en majuscule et pas pour générer les permutations ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
char mot[11] = "AAAAAAAAAA";
char *ptr = mot + 10;
while(1) {
  printf("%s\n",mot);
  char *ptr2 = ptr;
  while (*ptr2 == 'Z') {
    if (ptr2 == mot) goto fin;
    *ptr2-- = 'A';
  }
  (*ptr2)++;
}
fin:;

Tiens, pour rigoler, et puisqu'on est dans la rubrique algorithimique (et non "concours du programme C le plus crade"), tu pourrais

1. Nous dire ce que fait ton programme
2. le prouver

Ca te donnera peut être envie d'apprendre à programmer proprement :-D

[acx01b]

salut

je ne trouve pas ces lignes crades ^^
tous les algorithmes d'énumérations combinatoires sont par définitions crades
celui ci est probablement l'un des plus simples ?

il génére tous les mots en majuscules:

on démarre avec le tableau AAAAAAAAAA

à chaque itération on se place sur la dernière lettre:
- on affiche le tableau
- tant qu'on a un Z on met A à la place et se place sur la lettre juste avant
- une fois qu'on est sur une case qui ne contient pas Z on l'incrémente
- le test d'arret c'est si toutes les cases sont à Z

ainsi on a énuméré tous les mots majuscules de 10 lettres

la preuve c'est que c'est le même principe qui permet de compter avec les nombres décimaux (passage de 98 à 99 puis de 99 à 100...) appris en primaire

[alex_pi]

salut

je ne trouve pas ces lignes crades ^^

Moi si :-) Déjà, un goto... Mais au fait, avant de "le démontrer", vu que c'est un exemple trivial, tu aurais pu l'exécuter nan ? Tu te serais par exemple apperçu que ton "+ 10" était faux et aurait du être un "+9", parce que là, tu effaces joyeusement le \000 final, et le printf imprime des octet jusqu'à en trouver un autre (sur le code produit par mon gcc, c'est une 20aine d'octets plus loin, on a de la chance)

tous les algorithmes d'énumérations combinatoires sont par définitions crades
celui ci est probablement l'un des plus simples ?

C'est l'un des plus simple, et tu arrives à le rendre totalement illisible

il génére tous les mots en majuscules:

on démarre avec le tableau AAAAAAAAAA

à chaque itération on se place sur la dernière lettre:
- on affiche le tableau
- tant qu'on a un Z on met A à la place et se place sur la lettre juste avant
- une fois qu'on est sur une case qui ne contient pas Z on l'incrémente
- le test d'arret c'est si toutes les cases sont à Z

ainsi on a énuméré tous les mots majuscules de 10 lettres

la preuve c'est que c'est le même principe qui permet de compter avec les nombres décimaux (passage de 98 à 99 puis de 99 à 100...) appris en primaire

J'espère que tu es conscient de ne *rien* prouver ?

Prenons une autre version du code

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
(* module pour permetre l'impression sur la sortie standard *)
open Printf
 
(* longueur de la chaine dont on veut produire l'ensemble des permutations *)
let l = 4
 
(* enum_n_premier prend une chaine s en entrée et énumère toutes les
   chaines obtenues avec toutes les permutations de ses n + 1 premiers
   caractères. L'écriture est en style impératif pour être plus
   lisible par le formum "algorithmique". L'appel à n = -1 déclanche
   l'impression
*)
let rec enum_n_premier s n =
  if n < 0 then printf "%s\n" s else
    for i = (int_of_char 'A') to (int_of_char 'Z') do
      s.[n] <- char_of_int i;
      enum_n_premier s (n - 1);
    done
 
(* création de la chaine, et appelle de la fonction d'énumération sur la 
    longeur de la chaine *)
let _ =
  let s = String.make l 'A' in
    enum_n_premier s (l - 1)

On montre ici facilement que pour n = 0, enum_n_premier s n énumère bien l'ensemble des chaine à 1 caractère variant de A à Z. Puis par récurence, si pour un n fixé, enum_n_premier s (n -1) énumère l'ensemble des chaines à n caractères variants entre A et Z, enum_n_premier s n énumère l'ensemble des chaines à n + 1 caractère, en faisant varier le n + 1 eme caractère de A à Z et en énumérant à chaque fois toutes les chaines possibles.

On obtient donc ce que l'on veut, bien plus proprement, de façons lisible, et au final aussi concise.

[Jean-Marc.Bourguet]

Suis-je le seul a ne pas voir de differences fondamentales entre les programmes d'Alex et d'acx01b? Enlever la recursion du programme d'Alex (elle n'est pas terminale mais expliciter la pile puis remarquer qu'il y a un lien arithmetique entre le pointeur et les valeurs contenues fait a priori l'affaire) doit donner quelque chose de tres proche de ce que propose acx01b.

Une autre maniere de voir le rapport -- vraissemblablement plus proche du raisonnement par lequel acx01 a optenu directement le resultat --, c'est d'effectuer une operation de renversement de controle semblable a ce qu'on fait quand on implemente un algo de parcours sous forme d'iterateur ou de generateur.

[Jedai]

Et bien puisqu'on parle d'impératif et de fonctionnel, voici une solution à l'aspect plus fonctionnel en Haskell :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
import Control.Monad
 
main = putStr $ unlines $ replicateM 10 ['A'..'Z']

Qui utilise la fonction replicateM pour effectuer 10 fois de suite un choix dans ['A'..'Z'] (la liste des majuscules) de toutes les façons possibles (en utilisant en fait la monade des listes).

--
Jedaï

[PRomu@ld]

J'aimerai rappeler que la discussion originale est la recherche d'un algorithme pour générer des permutations. Par conséquent, si vous souhaitez discuter du bienfait de tel ou tel langage, cela n'a pas sa place ici.