Discussion :

[blackbird1]

salut,
j'essaye de coder un programme qui prend comme données :
- la taille d'une chaîne de caractères.
- la chaîne de caractères.
- la taille des mots à générer à partir de cette chaîne.
exemple :

4
bimp
2

le programme doit afficher :

12
bi
bm
bp
ib
im
ip
mb
mi
mp
pb
pi
pm

12 : est le nombre de mots générer.

j'ai codé ça :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
void BruteForce (int Nbre);
 
int TailleMot = 0;
int TailleMotGenerer;
int TailleChaineSource;
char *ChaineSource = NULL;
char *Mot = NULL;
 
int main(void) {
  int Total = 1;
  int Compteur;
 
  fscanf(stdin,"%d",&TailleChaineSource);
  ChaineSource = (char*)malloc(TailleChaineSource+1);
  fscanf(stdin,"%s",ChaineSource);
 
  fscanf(stdin,"%d",&TailleMotGenerer);
  Mot = (char*)malloc(TailleMotGenerer+1);
  for (Compteur = 0;Compteur <TailleMotGenerer;Compteur++)
    Total *= TailleChaineSource;
 
  fprintf(stdout,"%d\n",Total);
  BruteForce(TailleMotGenerer);
 
  free(Mot);
  free(ChaineSource);
 
  return 0;
}
 
 
 
void BruteForce (int Nbre) {
  int ParcouLettre;
  if (Nbre == 0 ) {
    Mot[TailleMot] = 0;
    fprintf(stdout,"%s\n",Mot);
    return;
  }
  for (ParcouLettre=0;ParcouLettre<TailleChaineSource;ParcouLettre++) {
    if (strrchr(Mot,ChaineSource[ParcouLettre]) == NULL) {
      Mot[TailleMot] = ChaineSource[ParcouLettre];
      TailleMot++;
      BruteForce(Nbre-1);
      TailleMot--;
    }
  }
}

sauf que le code affiche :

16
bi
bm
bp
ib
im
ip
mb
mi
mp

il affiche 16 au lieu de 12 (j'ai pas su trouvé la formule exacte pour afficher le nombre de mots où les lettres ne se répètent pas, on ne demande pas d'utiliser les calculs combinatoires).
Et il manque :

pb
pi
pm

j'arrive pas la résoudre.
merci.

[Neckara]

Bonjour,

Force brute : tu te fait une liste chaînée de tout tes mots triés par l'ordre alphabétique et tu n'insère un nouveau mot que s'il n'est pas encore présent dans la liste.

Force moins brute :
Tu trie ta première chaine de caractère, tu supprimes les doublons (?).
Et à partir de là, on doit pouvoir faire pas mal de combinaison.

Tu devrais aussi éviter d'utiliser des variables globales.

Code :

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

1
2
3
 
for (Compteur = 0;Compteur <TailleMotGenerer;Compteur++)
    Total *= TailleChaineSource;

Total = TailleChaineSource^TailleMotGenerer = 2^4 = 16

Si tu veux afficher le nombre de mots trouvé, il faut tout simplement que tu stocke tes mots dans ta liste chaînée et que tu incrémente un compteur à chacun insertions.

[pythéas]

Si tu veux afficher le nombre de mots trouvé, il faut tout simplement que tu stocke tes mots dans ta liste chaînée et que tu incrémente un compteur à chacun insertions.

C'est pas faux mais ça ressemble beaucoup à un exercice, il est possible qu'il doive faire le calcul séparément, de toute façon c'est du dénombrement de base du coup, il me parait important de souligner l'erreur :

si il n'y a pas de répetition dans la nouvelle chaine, la première lettre (du résultat) peut être n'importe laquelle des lettres de la chaine de base, la suivante n'importe laquelle sauf la précédente et ainsi de suite (les 2 précédentes, les 3...)

Code :

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

1
2
for (Compteur = 0;Compteur <TailleMotGenerer;Compteur++)
    Total *= TailleChaineSource - Compteur;

Après, il faut tenir compte des cas limites etc. mais c'était juste une tentative de clarification d'un point qui semble un peu confus pour le PO

[blackbird1]

salut,
Merci Neckara et pythéas pour vos réponse.
j'essaye de ne pas générér des le début les mots qui contiennent des doublons (au moment de la génération).

for (ParcouLettre=0;ParcouLettre<TailleChaineSource;ParcouLettre++) {
if (strrchr(Mot,ChaineSource[ParcouLettre]) == NULL) {
Mot[TailleMot] = ChaineSource[ParcouLettre];
TailleMot++;
BruteForce(Nbre-1);
TailleMot--;
}
}

"Mot" : va contenir les mots générés. cette condition "strrchr(Mot,ChaineSource[ParcouLettre]) == NULL" teste si la lettre "ChaineSource[ParcouLettre]" qu'on va mettre dans "Mot" exsite ou pas.
si elle existe : on passe à la lettre suivante. "for...".
si elle n'existe pas : on l'ajoute à "Mot".

par exemple :
par exemple:
pour

4
bimp
2

le programme prend "b"
Mot = NULL
"b" n'exsite pas dans "Mot"
Mot = "b"

puis il prend "b"
Mot = "b"
"b" existe dans "Mot"

il prend "i"
Mot = "b"
"i" n'existe pas dans "Mot"
Mot = "bi"

il affiche "bi"

et ainsi de suite...

franchement je vois pas pourquoi ce code marche pas, pour :

4
bimp
2

il n'affiche pas la totalité des mots générés :

12
bi
bm
bp
ib
im
ip
mb
mi
mp

il n'a pas affiché :

pb
pi
pm

merci

[pythéas]

Quand tu arrives à "mp", tu passes à ParcouLettre = 3 donc à ChaineSource[ParcouLettre] = 'p' et Mot vaut encore "mp" au moment où tu fais ton test :

Code :

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

if (strrchr(Mot,ChaineSource[ParcouLettre]) == NULL)

Tu fais donc un :

Code :

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

if (strrchr("mp",'p') == NULL)

je te laisse deviner le résultat...

si par exemple tu ajoutes

Code :

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

Mot[1]=' ';

après le corps du if tu auras ton résultat mais ce n'est pas ça qu'il faut faire
essaye de faire quelque chose d'un peu plus prôpre, évite notament les variables globales (tu peux observer le temps que tu as sans doute perdu à cause de la variable Mot dont tu ne maîtrisait pas la valeur)

[gheaeckkseqrz]

Ce que tu veux faire ça s'appelle générer des combinaisons.

En maths ca s'ecrit = Cnk (avec le n en indice et le k en exposant)

Dans ton cas n = 2 et k = 4.

Le problème si tu vérifie a chaque fois que ton mot n'as pas déjà été écrit et qu'il est valide, c'est que pour des n et des k plus grand, ton temps de calcul vas exploser.

Donc :
Etape 1 : supprimer les doublons dans la chaîne source.
Etape 2 : Le nombre de combinaison possible et égal a

Etape 3 : Generez les combinaisons


Le code est en C++ désolé.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void            comb(std::vector<char> v, std::vector<char> &v2, int n, int m)
{
  if ((int)v2.size() < m)
    {
      for (unsigned int i(v2.size()) ; i < v.size() ; ++i)
        {
          if (v[i] != -1)
            {
              v2.push_back(v[i]);
              v[i] = -1;
              comb(v, v2, n + 1, m);
              v2.pop_back();
            }
        }
    }
  else
    {
         // affichage de mot génèré
    }
}

Je pense que c'est la méthode la plus optimisée pour faire ce que tu veux faire.