Algorithmique

[oli1978]

Bonjour,

J'ai un petit probleme que je vous serais reconnaissant de m'aider a resoudre.
Alots, j'ai un tableau a n lignes, chaque ligne ayant un nombre different de colonnes. Par exemple, ca peut donner ca :

1
5 7
8 9
1 7 3

Ce que je voudrais, c'est pouvoir construire toutes les combinaisons possibles. A savoir pour cet exemple :

1 5 8 1
1 5 8 7
1 5 8 3
1 5 9 1
1 5 9 7
1 5 9 3
1 7 8 1
1 7 8 7
1 7 8 3
1 7 9 1
1 7 9 7
1 7 9 3

Est ce que vous avez une idee d'algo pour realiser ce genre de chose ?

Merci d'avance

Olivier
-----

[Coincoin]

Salut,
Utilise l'algorithme que tu as intuitivement utilisé pour nous donner toutes les combinaisons ! Tu décales la dernière ligne, et quand tu as fini, tu décales d'un cran la ligne supérieure. Pour ça, rien de plus simple, il suffit d'imbriquer plein de boucles for.
for i from 1 to "taille de la ligne 1"
for j from 1 to "taille de la ligne 2"
...
for schtroumpf from 1 to "taille de la ligne n"
do ligne1[i] ligne2[j]... lignen[schtroumpf]
endfor
endfor
...
endfor

Si le nombre de lignes changents, ça se complique, mais ça se fait encore (avec une boucle for pour décrire les lignes).
T'utilises quoi comme langage ?

[oli1978]

Salut,
Utilise l'algorithme que tu as intuitivement utilisé pour nous donner toutes les combinaisons ! Tu décales la dernière ligne, et quand tu as fini, tu décales d'un cran la ligne supérieure. Pour ça, rien de plus simple, il suffit d'imbriquer plein de boucles for.
for i from 1 to "taille de la ligne 1"
for j from 1 to "taille de la ligne 2"
...
for schtroumpf from 1 to "taille de la ligne n"
do ligne1[i] ligne2[j]... lignen[schtroumpf]
endfor
endfor
...
endfor

Si le nombre de lignes changents, ça se complique, mais ça se fait encore (avec une boucle for pour décrire les lignes).
T'utilises quoi comme langage ?

Du C++.
Evidemment, le nombre de possibilites est variable, mais on peut le calculer. Pour l'exemple que j'ai donne, on l'a simplement en multipliant le nombre de colonnes de chaque ligne, soit 1*2*2*3=12.

[Coincoin]

Ok, je connais pas le C++, mais avec mes maigres connaissances de C, je ferais un pointeur de pointeur, une sorte de tableau à deux entrées. La première entrée indique la ligne, la deuxième t'indique l'élément dans la ligne. Le seul truc, c'est qu'il faut aussi connaître la taille de chaque ligne (tu peux le stocker dans un autre tableau) , et le nombre de lignes.
Il reste plus qu'à enlever ma longue liste de for, en faisant un for sur les lignes. Normalement, avec 3 boucles for imbriquées, tu dois pouvoir t'en sortir.

[A voir en vidéo sur Futura]

[oli1978]

Ok, je connais pas le C++, mais avec mes maigres connaissances de C, je ferais un pointeur de pointeur, une sorte de tableau à deux entrées. La première entrée indique la ligne, la deuxième t'indique l'élément dans la ligne. Le seul truc, c'est qu'il faut aussi connaître la taille de chaque ligne (tu peux le stocker dans un autre tableau) , et le nombre de lignes.
Il reste plus qu'à enlever ma longue liste de for, en faisant un for sur les lignes. Normalement, avec 3 boucles for imbriquées, tu dois pouvoir t'en sortir.

Merci CoinCoin.
Je comprends bien le principe, mais je suis incapable de le coder !
Tu me dis 3 boucles for. La 1ere sert a boucler sur le nombre de lignes. Les 2eme et 3 eme bouclent sur quoi ? C'est la que je bloque ...

Mes structures de donnes sont comme ca :

** le tableau de base est un PILE de PILE :
candidats = [ [1] [5 7] [8 9] [1 7 3] ]
Je peux connaitre la taille de candidats et de candidats(i) comme ca :
taille_cand = candidats.size() et taille_cand(i) = candidats(i).size()

** en sortie, je voudrais une structure de donnees identique :
possibles = [ [1 5 8 1] [1 5 8 7] [1 5 8 3] [1 5 9 1] ... [1 7 9 3] ]
Peu importe l'ordre dans lequel sont stockes les possibles, je m'en arrangerais tres bien.

** pour rajouter une element dans une PILE , j'utilise l'operateur "<<". Par exemple pour rajouter une ligne dans possibles, je fais un truc de cet ordre : possibles << NULL; ensuite, je peux faire : possibles(0) << candidats(i)(j).

Je ne te demande pas de m'ecrire le code (bien que je sois fortement tente ...), mais un dernier coup de pouce m'eclairerait bien ...

Merci de ton aide