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
Bonjour !

Je suis étudiant et je débute en programmation ... Je voudrais en fait créer un programme pour trouver un mot en générant toutes les combinaisons possibles de l'alphabet ( connaissant la longueur du mot évidemment )et ensuite les tester par rapport au mot rentrer par l'utilisateur.

Je pense que ca peut se réaliser avec autant de boucles que de caractères. Mais le programme peu prendre des mots de plusieurs tailles ( jusqu'à milles ).

On m'a dit que c'était possible avec une fonction récursive mais je n sais pas bien comment m'y prendre

Si je pouvais avoir une petite piste pour me lancer ce serait génial.

Merci d'avance ...
A voir également:

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

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,
0
Rejoignez-nous