Générer toutes le combinaisons possibles d'une chaîne de caractères
tuvistavie1989
Messages postés
1
Date d'inscription
mardi 30 mars 2010
Statut
Membre
Dernière intervention
30 mars 2010
-
30 mars 2010 à 19:22
benjafri Messages postés 2 Date d'inscription jeudi 18 octobre 2012 Statut Membre Dernière intervention 17 octobre 2012 - 27 mai 2010 à 10:04
benjafri Messages postés 2 Date d'inscription jeudi 18 octobre 2012 Statut Membre Dernière intervention 17 octobre 2012 - 27 mai 2010 à 10:04
A voir également:
- Générateur de combinaison lettres
- Générateur de combinaison de mots - Meilleures réponses
- Générateur de chiffre et lettre - Meilleures réponses
- COMBINAISON DE LETTRES ✓ - Forum Visual Basic
- Aide générateur de combinaison ✓ - Forum VB.NET
- Générateur de lettre ✓ - Forum VB.NET
- Générer tous les permutations admissibles - Forum Java
- Trouver les combinaisons possibles - Forum C / C++ / C++.NET
2 réponses
cs_Chouchou182
Messages postés
252
Date d'inscription
vendredi 13 juin 2003
Statut
Membre
Dernière intervention
25 avril 2011
1
31 mars 2010 à 01:01
31 mars 2010 à 01:01
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):
Ç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:
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,
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):
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 ""
Ç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:
#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,
