Générer toutes le combinaisons possibles d'une chaîne de caractères

Signaler
Messages postés
1
Date d'inscription
mardi 30 mars 2010
Statut
Membre
Dernière intervention
30 mars 2010
-
Messages postés
2
Date d'inscription
jeudi 18 octobre 2012
Statut
Membre
Dernière intervention
17 octobre 2012
-
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 ...

2 réponses

Messages postés
252
Date d'inscription
vendredi 13 juin 2003
Statut
Membre
Dernière intervention
25 avril 2011

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,
Messages postés
2
Date d'inscription
jeudi 18 octobre 2012
Statut
Membre
Dernière intervention
17 octobre 2012

BJF