Génération de combinaisons à partir d'une chaine numérique

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 :

Citation:

---

00 01 02
10 11 12
20 21 22

---

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

Citation:

---

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 :

Citation:

---

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.

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?

Considère une classe trit telle que:

Code:

---

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:

---

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

Citation:

---

Envoyé par phi1981

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.

Citation:

---

Envoyé par leternel

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.

Citation:

---

Envoyé par 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?

---

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 :(

Citation:

---

Envoyé par leternel

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.

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

Citation:

---

Envoyé par Obsidian

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:

---

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.

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.

En fait, je ne sais pas pourquoi tu t'embêtes à manipuler des chaînes de caractères...
L'idée est plus simple que ça: il te suffit de compter de 0 jusqu'à 3 puissance 3 (la base dans laquelle tu travailles puissance le nombre de chiffres que tu veux). Pour ça, une bête boucle for avec l'incrémentation d'un int.
A chaque itération, tu convertis cet int en une chaîne de caractères en base 3. Tu ne peux pas utiliser sprintf() pour ça, parce qu'à ma connaissance il ne permet pas de choisir la base utilisée (hexa ou décimal uniquement). Mais une autre fonction (itoa() si elle est standard, ou une que tu écrirais toi même) peut très bien le faire.

Sauf que les caractères fixes rendent le problème plus délicat.

leternel: bien vu... j'avais oublié ce détail. Désolé.

Citation:

---

Envoyé par leternel

Sauf que les caractères fixes rendent le problème plus délicat.

---

Ce n'est pas un problème, il suffit d'une fonction d'affichage qui gère ces cas (il suffit d'insérer X au bon encdroit), le principe de décompte expliqué par Obsidian reste le même.
Cà se fait sur le principe

Code:

---

1 2 3 4

initialisation(chaine) faire afficher(chaine) tant que incrementer(chaine) == possible

---

Citation:

---

Envoyé par phi1981

En fait, je ne sais pas pourquoi tu t'embêtes à manipuler des chaînes de caractères...
L'idée est plus simple que ça: il te suffit de compter de 0 jusqu'à 3 puissance 3 (la base dans laquelle tu travailles puissance le nombre de chiffres que tu veux). Pour ça, une bête boucle for avec l'incrémentation d'un int.
A chaque itération, tu convertis cet int en une chaîne de caractères en base 3.

---

Donc, tu reviens bien à une chaîne de caractères. Autant les incrémenter directement dans ce cas.

Citation:

---

Tu ne peux pas utiliser sprintf() pour ça, parce qu'à ma connaissance il ne permet pas de choisir la base utilisée (hexa ou décimal uniquement). Mais une autre fonction (itoa() si elle est standard, ou une que tu écrirais toi même) peut très bien le faire.

---

C'est cette fonction qu'il cherche à écrire. Incrémenter un entier en binaire puis le convertir sa base à l'aide de modulos successifs est aussi compliqué à assimiler du point de vue du programmeur, et encore plus complexe sur un plan strictement algorithmique.

Citation:

---

Envoyé par leternel

Sauf que les caractères fixes rendent le problème plus délicat.

---

À la limite, si tu disposes déjà d'une fonction exprimant dans une base donnée, tu génères la chaîne et tu l'affiche caractère par caractère, en insérant les symboles fixes aux bons moments.

Il en reste que toute la discussion a pour objet l'algorithme à suivre, et son éventuelle implémentation en langage C. Si tout le problème se résume simplement à obtenir ces combinaisons d'une manière ou d'une autre, alors il s'agit d'un simple produit cartésien. Ça se fait par exemple en une ligne de bash :

Code:

---

1 2	$ echo {0..2}{0..2}X{0..2} 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

---

Bonjour à tous,

Après une bonne nuit de sommeil, j'ai enfin trouvé la solution !!! C'est fou comment j'ai buté sur un algo aussi simple :aie:

Voilà la code pour ceux qui passeront dans le coin :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

while (index >= 0) { puts(buffer); index = strlen(buffer) - 1; while (index >= 0) { buffer[index]++; if (buffer[index] != '3') break; else { buffer[index] = '0'; index--; } } }

---

Merci Obsidian pour tes conseils, cela m'a bien aidé :)

PS : Le but n'était pas d'utiliser des fonctions comme itoa pour générer mes combinaisons, effectivement en 2 lignes ca se fait très bien mais ce n'était pas le but et puis avec mon histoire de position fixe, ce n'était pas possible avec itoa ou équivalent.

Après gérer le cas où certains chiffres sont fixes est facile à partir de l'algo ;)

Encore merci à vous.

J'aurai pas fait tout à fait comme toi (pseudo code inspié du C)

Code:

---

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

debut initialiser(str) faire afficher(str) incrementer(str) tant que incrementer(str) == possible fin   // pourquoi cette fonction // elle permet de gerer le cas de positions réservées pour X // voir premier post procédure afficher(str) debut .... fin   fonction incrementer(str) retourne {possible ; pas possible} debut i <- longueur(str) - 1 str[i] <- str[i] + 1 tant que str[i] == max faire si i == 0 alors retourner pas possible   str[i] <- '0' str[i-1] <- str[i-1] + 1 i <- i - 1 fin tant que   retourner possible fin

---

Cela permet de ne pas rentrer forcément dans la boucle while intrerne.