Discussion :

[fred_sell]

bonsoir

voila un petit problème :

Dans mon petit programme, on demande d'entrer un mot terminer par un point '.'
et on stocke les caractères dans un tableau dynamique "A" à une seule dimension, on récupère le nombre (n) de caractères dans ce mot, on crée ensuite un tableau dynamique "tab" à deux dimensions où on a :
(nbr de colonnes = n ; nbr de ligne = n!), chaque ligne du tableau "tab" contiendra une anagramme différente de votre mot.

jusqu'à la création du tableau "tab" il n'y a pas de problème, à vraie dire je me bloque dans le remplissage du tableau tab, voilà ce que j'ai fait :

les deux fonction principale ;

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
int verify(char**tab , int k , int j , char c) //vérification du double
{
    int i, t=1;
    for(i=0 ; i<=j-1 ; i++)
    {
        if(tab[k][i]==c)
        t=0;
    }
 
    if(t==1)
    return 1;        //c'est que "t" n'a pas changé de valeur
 
    return 0;       //le sinon
}
 
 
void anagram(char*A , char**tab , int n)   //remplissage de tab
{
 
    int i, j, k;
 
    for(j=0 ; j<=n-1 ; j++)         //j est l'indice de colones de "tab"
    {
        for(i=0 ; i<=n-1 ; i++)       // i est l'indince de "A"
        {
            for(k=i*fact(n-1-j) ; k<=(i+1)*(fact(n-1-j)) ; k++)      //k est l'indice de lignes de "tab"
            {
                if(verify(tab,k,j,A[i])==1)
                tab[k][j]=A[i];
 
                else          //sinon on 
                {
                    i++;
                    k--;
                }
            }
        }
    }
 
}

si vous avez une idée...............merci!!

[Invité(e)]

Bonjour,

J'ai bien en tête une idée d'algorithme pour ç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
 
chaine : mot de départ
chaine : mot courant
chaine : mot test
chaines : liste des anagrammes.
entier : N
 
N = taille du mot de départ
mot courant = mot de départ 
TANT QUE VRAI
   I = 0
   TANT QUE I < N
      mot test = interversion(N-I, N-I-1, mot courant)
      SI mot test est dans liste des anagrammes
      ALORS
         I = I + 1
      SINON
         ajouter mot test à la liste des annagrammes
         mot courant = mot test
         SORTIE TANT QUE
      FIN SI
      SI N =I
         SORTIE TANT QUE
      FIN SI
   FIN TANT QUE
FIN TANT QUE

Exemple : Avec N = 3
Mot de départ = 123
On va ajouter à la liste d'anagrammes :
ABC
inversion 2 / 3
ACB
inversion 2 / 3 --> ABC déjà dans la liste
inversion 1 / 2
CAB
inversion 2 / 3
CBA
inversion 2 / 3 --> CAB déjà dans la liste
inversion 1 / 2
BCA
inversion 2 / 3
BAC
inversion 2 / 3 --> BCA déjà dans la liste
inversion 1 / 2 --> ABC déjà dans la liste
i = 3, on sort

[fred_sell]

et ça marche votre algorithme avec un mot de 4 ou 5 caractères ??

[Invité(e)]

et ça marche votre algorithme avec un mot de 4 ou 5 caractères ??

En pratique, il est compliqué à mettre en œuvre...

Il y a plus beaucoup plus simple : utiliser la récursivité :

Il faut se dire que l'ensemble des anagrammes de "ABCD" c'est :
A+l'ensemble des annagrammes de "BCD"
B+l'ensemble des annagrammes de "ACD"
C+l'ensemble des annagrammes de "ABD"
D+l'ensemble des annagrammes de "ABC"
...
l'ensemble des annagrammes de "BCD" c'est :
B + l'ensemble des anagrammes de "CD"
...
Et ainsi de suite


En pratique, on peut coder comme ç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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
void print_ana(char *head, char *str)
{
    static int k = 0;
    size_t sz = strlen(str);
    if(0 == sz) {
        return ;
    }
    if(1 == sz) {
        printf("%3d - %s%s\n", ++k, head, str);
    } else {
        size_t i;
        char headbuf[64], strbuf[64];
        for(i = 0; i < sz; ++i) {
            sprintf(headbuf, "%s%c", head, str[i]);
            /* on retire de str ce qu'on a mis dans la tete */
            strncpy(strbuf, str, i);
            strncpy(strbuf+i, str+i+1, sz-i);
            /* appel récursif */
            print_ana(headbuf, strbuf);
        }
    }
}
 
int main(void) 
{
    char head[64] = "";
    char str[64] = "chien";
    print_ana(head, str);    
 
    return 0;
}