Discussion :

[Aspic]

Bonjour à tous,

Je cherche un algorithme permettant de générer toutes les combinaisons possibles à partir de la taille d'une chaine numérique.

Exemples :
Soit la chaine str = "00" (taille = 2), sachant que chaque caractère peut prendre la valeur 0, 1 ou 2 je souhaite avoir :

00 01 02
10 11 12
20 21 22

avec la chaine str = "000" (taille = 3),

000 001 002
010 011 012
020 021 022
100 101 102
110 111 112
120 121 122
200 201 202
210 211 212
220 221 222

Pour str = "0000" (taille = 4), on a 3^4 = 81 possibilités

Dans un second temps, j'aurais besoin de dire que certaines positions ne changeront pas.

Exemple : str = "00X0" (taille = 4 mais seulement 3 positions changent), je voudrais avoir :

00X0 00X1 00X2
01X0 01X1 01X2
02X0 02X1 02X2
10X0 10X1 10X2
11X0 11X1 11X2
12X0 12X1 12X2
20X0 20X1 20X2
21X0 21X1 21X2
22X0 22X1 22X2

Quelque soit la valeur de X, il ne doit pas être modifié.

Je sèche sur l'algorithme reccursif (oui car je pense qu'il doit être recursif), je n'ai jamais été très à l'aise avec la récursivité

Merci à vous et bonne journée.

[phi1981]

Personnellement, je n'imagine pas cet algorithme comme étant récursif.

En fait, tout ce que tu essayes de faire, c'est compter en base 3 (après tout, c'est comme ça que tu as fait, toi humain, pour nous donner l'exemple). Donc c'est juste une affaire de conversion de base, ou bien y a quelque chose que je n'ai pas compris?

[ternel]

Considère une classe trit telle que:

Code :

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

1
2
3
4
5
6
7
class trit {
private:
    unsigned char value;
public:
    trit() : value(0) {}
    bool operator++() {return ((++value)%=3)==0;}
};

Avec ca, et un vector<trit>, tu dois pouvoir t'occuper de toute la première partie.

Code :

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

1
2
3
4
5
6
while(je sais pas trop quoi pour dire si on n'a pas encore tout affiché) {
    for (std::vector<trit>::const_iterator it = trits.begin(), end = trits.end(); it!=end && ++*it; ++it);
    for (auto const& trit : trits) {
        cout << trit;
    }
}

On parle de C, ici

[Obsidian]

En fait, tout ce que tu essayes de faire, c'est compter en base 3 (après tout, c'est comme ça que tu as fait, toi humain, pour nous donner l'exemple). Donc c'est juste une affaire de conversion de base, ou bien y a quelque chose que je n'ai pas compris?

+1 ! Ce n'est qu'une énumération des plus classiques. L'algorithme est tout simplement celui qu'on applique à la base 10 depuis la petite enfance.

Aspic : tu initialises une chaîne à « 0000 » de la longueur de ton choix, tu l'affiches, puis tu incrémentes le chiffre le plus à droite, donc en le faisant passer à l'élément immédiatement suivant dans l'ensemble des chiffres (ou des symboles, en général) que tu veux voir représenter. Si tu t'aperçois que tu sors de l'ensemble, alors tu le ramène à zéro (ou au premier symbole) et tu incrémentes celui qui est immédiatement à sa gauche, en appliquant le même procédé : remise à zéro si dépassement et incrémentation du voisin. Quand tu t'aperçois que tu viens de remettre à zéro le chiffre le plus à gauche de ta chaîne, alors tu as passé en revue toutes les combinaisons possibles.

Tu peux t'en sortir sans récursivité aucune avec deux boucles imbriquées seulement.

Considère une classe trit telle que: Avec ca, et un vector<trit>, tu dois pouvoir t'occuper de toute la première partie.

Ici, nous sommes dans le forum C et les solutions à base de classe de la lib C++ standard ne sont pas applicables.
De plus, le problème est essentiellement algorithmique. Les lier directement à une solution technique n'est pas recommandable.

[Aspic]

Aspic : tu initialises une chaîne à « 0000 » de la longueur de ton choix, tu l'affiches, puis tu incrémentes le chiffre le plus à droite, donc en le faisant passer à l'élément immédiatement suivant dans l'ensemble des chiffres (ou des symboles, en général) que tu veux voir représenter. Si tu t'aperçois que tu sors de l'ensemble, alors tu le ramène à zéro (ou au premier symbole) et tu incrémentes celui qui est immédiatement à sa gauche, en appliquant le même procédé : remise à zéro si dépassement et incrémentation du voisin. Quand tu t'aperçois que tu viens de remettre à zéro le chiffre le plus à gauche de ta chaîne, alors tu as passé en revue toutes les combinaisons possibles.

Merci pour l'aide, j'ai essayé avec cette solution :

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
#define TAILLE 3
int main()
{
    int i, j, len = 0, index = 0;
    char str[TAILLE+1] = {0};
    char buf[TAILLE+1] = {0};
 
    for (i=0; i<TAILLE; i++)
       str[i] = '0';
 
    len = strlen(str) - 1;
    index = len;
 
    while (index >= 0)
    {
        strncpy(buf, str, TAILLE+1);
        //puts(buf);
 
        for(j=0; j<3; j++)
        {
            puts(buf);
            buf[len]++; // incrémente le chiffre le plus à droite
        }
 
        // ici on sort de l'intevalle [0, 3[
        // ICI ca doit être faux !
        index--;
        str[index]++;
    }
 
    return 0;
}

Mais ca ne marche pas tout à fait, je n'ai pas la bonne sortie.

[Obsidian]

Il y a de l'idée mais ton programme n'est pas tout-à-fait exact : en fait, à chaque fois que tu passes d'une combinaison à la suivante, tu dois modifier entre 1 et n symboles, potentiellement tous : c'est le cas, par exemple, quand tu passes de « 022 » à « 100 ». Il te faut donc :

• Une boucle while principale au début de laquelle tu affiches systématiquement le contenu de ton buffer, puis repositionne l'index sur le chiffre le plus à droite ;
• Une boucle while imbriquée à la seconde dans laquelle tu restes tant qu'il est nécessaire d'incrémenter des chiffres.

Astuce : le plus simple est de rester dans la boucle imbriquée tant que l'index est positif ou nul, comme tu le fais, et d'en sortir avec un break. Tu peux alors examiner le même index sous les mêmes conditions pour sortir de la boucle principale.

Si ce n'est toujours pas clair, alors demande-toi comment tu procèdes naturellement avec les nombres entiers. Si je te demande « jusqu'à combien tu sais compter ? », tu vas me répondre que tu n'as virtuellement aucune limite. Pourtant, ta mémoire n'est pas infinie et à aucun moment tu n'as appris les nombres entiers par cœur dans leur ensemble, ou dans un sous-ensemble suffisamment grand (sauf pour apprendre à les nommer, bien sûr). La solution à ce mystère est le fait d'avoir une méthode unique, toujours la même, qui s'applique à n'importe quel nombre. C'est précisément cette méthode qu'il faut utiliser dans ton programme.

[Aspic]

Personnellement, je n'imagine pas cet algorithme comme étant récursif.

En fait, tout ce que tu essayes de faire, c'est compter en base 3 (après tout, c'est comme ça que tu as fait, toi humain, pour nous donner l'exemple). Donc c'est juste une affaire de conversion de base, ou bien y a quelque chose que je n'ai pas compris?

Ce n'est pas aussi simple que cela, car il ne s'agit non pas d'afficher 0, 1, 2, 10, 11, 12 ... mais des chaines comme "000" "001" "002" "010" "011" "012"... (pour taille = 3)
un simple modulo ne suffit pas. Enfin, je suis un peu perdu dans cet algo

for (std::vector<trit>::const_iterator it = trits.begin(), end = trits.end(); it!=end && ++*it; ++it);
for (auto const& trit : trits) {
cout << trit;
}

Je n'ai rien compris au code et c'est du C++. Je préfererais juste un algo Et je ne suis pas sur d'avoir en sortie ce que je souhaite.

[ternel]

Oublie, je me suis complètement emmelé entre le C et le C++.