Salut,
Pensons «récursif».
Imaginons un alphabet de deux lettres seulement, A et B.
Énumérer tous les mots de longeur n, c'est énumérer tous les mots commençant par la lettre A et dont la suite est de longueur (n-1) puis énumérer tous les mots commençant par la lettre B et dont la suite est de longueur (n-1).
Énumérer tous les mots de longueur zéro, c'est facile !
Ainsi, on peut, par exemple, écrire le code qui suit (ocaml, naïf):
[code]
let rec enum_aux : string -> int -> string list =
fun dbt -> function
| 0 -> [dbt]
| n -> enum_aux (dbt ^ "A") (n-1)
@ (enum_aux (dbt ^ "B") (n-1))
let enum : int -> string list =
enum_aux ""
[/code]
Ça semble marcher pour les mots jusqu'à (chez moi) 18 lettres: la pile de récursivité est pleine.
Qu'à cela ne tienne, virons la récursivité. Et ce-faisant, apprenons à compter.
En décimal.
D'abord, le chiffre des unités: 0, 1, 2... 9
Quand on a trop d'unités, on remet ce chiffre à zéro, et on incrémente le chiffre des dizaines: 1-0. Et on recommence: 1-1, 1-2,..., 1-9, 2-0,..., 9-9
Quand c'est le chiffre des dizaines qui est «plein» à son tour, c'est les centaines que l'on incrémente, et on revient aux unités.
Etc.
Ce qui peut donner, en C:
Code C/C++ :
#include<stdio.h>
#include<stdlib.h>
#include<errno.h>
#include<string.h>
enum alphabet {
A,
B,
FIN
};
const
char char_of_alphabet[FIN] =
{ 'A', 'B' };
void
print_mot(enum alphabet *mot)
{
while(*mot != FIN)
printf("%c", char_of_alphabet[*mot++]);
printf("\n");
}
int
enum_mots(size_t len)
{
enum alphabet *mot;
if (len == 0)
return 0;
mot = malloc((len + 1) * sizeof(*mot));
if (mot == NULL)
return 1;
memset(mot, A, len);
mot[len] = FIN;
size_t i = 0;
while (i < len)
{
print_mot(mot);
++ (*mot);
i = 0;
while (mot[i] == FIN && i < len)
{
mot[i++] = A;
++(mot[i]);
}
}
free(mot);
return 0;
}
int
main(int argc, char *argv[])
{
int res = enum_mots(argc-1);
if (res != 0)
perror("Échec");
return res;
}
NB: ce calcul est par essence de complexité exponentielle (base: taille de l'alphabet, exposant: longueur du mot); il y a peut-être une manière plus efficace d'arriver à ses fins...
Bonne prog,
--
Chouchou.