Discussion :

[henneka]

Bonjour,

Je cherche a résoudre le pb suivant :

comment verifier que tous les mots possibles avec les caracteres d'une chaine sont contenus dans un tableau de chaine :

Par ex : verifier que pour "abc", on a bien "abc","acb","abc", Etc ... contenus dans un tableau de string

J ai du mal avoir commen, pour la comparaison, on peut passer de "abc" a "acb"

apres un strcmp devrait faire l'affaire, je suppose.

par avance merci

[dalfab]

Bonjour,

Le problème doit se résoudre en plusieurs étapes.

Si on suppose que toutes les lettres du mot sont différentes, on pourrait :
* parcourir tous les mots et vérifier que chaque lettre du mot initial y est incluse.
* Et pour vérifier que tous les cas sont là. Les lettres sont différentes, donc il y a N! possibilités, avec N=strlen(mot). Il doit donc y avoir N! mots et tous les mots doivent être différents deux à deux.

Si le mot peut avoir des lettres en double, il faut une autre méthode plus complexe.

Dans tous les cas strcmp() ne sert à rien, mais on pourrait s'inspirer de son code et le modifier de pour écrire une fonction qui serait strsimilar():

Code :

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

1
2
3
4
5
6
7
8
9
10
int strcmp(const char* s1, const char* s2) {
   while ( *s1 == *s2  &&  *s1 != '\0'  &&  *s2 != '\0' ) {
      ++s1;
      ++s2;
   }
   // un des deux a atteint le bout ou on a trouvé une différence
   if ( *s1 == *s2 ) return 0;       // identiques jusqu'au bout
   if ( *s2 == '\0'  ||  *s1 > *s2 ) return 1; // s1 est supérieur
   return -1;                        // s2 est supérieur
}

[ternel]

Ton problème repose beaucoup sur la génération de la liste de toutes les permutations d'une séquence arbitraire.

Réponds juste avec un papier et un crayon aux questions suivantes:

• Quelles sont les permutations de {1}?
• Quelles sont les permutations de {1, 2}?
• Quelles sont les permutations de {3, 4}?
• Quelles sont les permutations de {1, 2, 3}?
• Quelles sont les permutations de {1, 2, 3, 4}?
• Comment as-tu trouvé toutes ces réponses?
• Si tu as toutes les permutations d'une séquence, quelles sont celles de la même séquence, augmenté d'un élément?