Discussion :

[juelo]

Bonjour,

Voici le pb : j'ai un tableau comme celui ci :
|a|b|
|c|d|e|
|f|g|h|
|i|j|

je dois en sortir ttes les combinaisons possibles (ici il y en a 2*3*3*2 = 36) :
a c f i
a c f j
a c g i
a c g j
a c h i
a c h j
a d f i
a d f j
a d g i
a d g j
a d h i
a d h j
a e f i
a e f j
a e g i
a e g j
a e h i
a e h j
(...la même chose avec en première lettre b)

J'ai pensé à faire une fonction récursive mais j'avoue que j'ai un peu mal à m'en sortir...

Merci bcp de me donner une piste...

[BugFactory]

Il faut utiliser des boucles imbriquées. Une boucle par tableau.

Code :

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

1
2
3
4
5
6
7
8
9
10
 
Pour chaque élément de tableau1
    Pour chaque élément de tableau2
        Pour chaque élément de tableau3
            Pour chaque élément de tableau4
                Renvoyer(élément1, élément2, élément3, élément4)
            Fin boucle4
        Fin boucle3
    Fin boucle2
Fin boucle1

Veuillez remarquer que j'ai oubliée la notation normalisée pour les algorithmes...

[juelo]

Ok pour la description du pb que j'ai faites...mais j'ai oublié un paramètre important : je ne connais pas le nombre de tableaux à parcourir, voici quelques cas pour illustrer :

ex:
|a|b|
|c|d|e|
|f|g|h|
|i|j|

ou

|a|b|c|d|e|
|i|j|

ou
|a|b|c|
|d|e|
|f|g|
|h|i|
|j|k|
...

Donc 'une boucle par tableau' ce n'est pas possible...

je reste à l'écoute, en attendant je cherche...

[BugFactory]

C'est toujours possible, simplement vous ne connaissez pas le nombre de boucles à imbriquer par avance. Il va falloir faire une boucle sur les boucles. Bon courage.

[Trap D]

Ça peut se traiter avec une structure de file et un marqueur de fin de file.

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
// intialisation
pour tous les éléments du premier tableau faire
  mettre dans la file l'élément
fin pour
mettre le marqueur de fin de file
// algo proprement dit
pour tous les tableaux restant faire
  tant que l'élément défile est différent du marqueur de fin de file faire
    pour tous les éléments du tableau en cours faire
       créer un nouvel élement en ajoutant en fin de liste l'élément du tableau
      ajouter ce nouvel élément dans la file
    fin pour
  fin tant que
  ajouter le marqueur de fin de file dans la file
fin pour

A la fin, la file contient tous les éléments voulus, ce n'est pas très efficace, mais ça fonctionne.

[pcaboche]

Tu programmes en quel langage?

En Prolog, c'est tout facile à faire:

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
combi([L|Q], [Elem|R]) :-
  member(Elem, L),
  combi(Q, R).
 
combi([], []).
 
 
 
combinaisons(Listes, Combis) :-
  findall(C, combi(Listes, C), Combis).
 
 
 
test :-
  combinaisons([[a,b], [c,d,e], [f,g,h], [i,j]], Combis),
  write('Combis = '), write(Combis), nl.

Exécution:

Code :

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

1
2
3
4
|?- test.
Combis = [[a, c, f, i], [a, c, f, j], [a, c, g, i], [a, c, g, j], [a, c, h, i], [a, c, h, j], [a, d, f, i], [a, d, f, j], [a, d, g, i], [a, d, g, j], [a, d, h, i], [a, d, h, j], [a, e, f, i], [a, e, f, j], [a, e, g, i], [a, e, g, j], [a, e, h, i], [a, e, h, j], [b, c, f, i], [b, c, f, j], [b, c, g, i], [b, c, g, j], [b, c, h, i], [b, c, h, j], [b, d, f, i], [b, d, f, j], [b, d, g, i], [b, d, g, j], [b, d, h, i], [b, d, h, j], [b, e, f, i], [b, e, f, j], [b, e, g, i], [b, e, g, j], [b, e, h, i], [b, e, h, j]]
 
Yes

Voilà, ça te donnera une idée de la manière de faire ça de façon récursive.

[juelo]

ok merci à tous je vais essayer de m'en sortir avec tt vos conseils !

pour info je programme en vb...

[Trap D]

Je doute qu'on puisse facilement adapter la méthode Prolog en VB.

[juelo]

c'est le moins que l'on puisse dire...

par contre j'e suis sur le point de tester ta méthode...

[pcaboche]

Je doute qu'on puisse facilement adapter la méthode Prolog en VB.

Moi aussi: ça m'étonnerait fort qu'on puisse faire la même chose en 10 lignes de VB seulement.

! Viva el Prolog !

***
Plus séreusement, pour faire la même chose dans un langage du genre de VB, on aurait besoin:
- d'un tableau avec les tailles de chaque liste (taille)
- d'un tableau avec la position actuelle dans la n-ième liste (pos)

Grâce à ces tableaux, on saurait où on en est dans la génération des différentes combinaisons (on prend le pos[1]-ième élément de la liste 1, pos[2]-ième élément de la liste 2, etc.).

[juelo]

ce pb ne m'inspire vraiement pas...si vs avez une soluce clé en main je suis preneur...affligeant d'en arriver là...

[méphistopheles]

Le problème, vient du fait que tu ne connais pas le nombre de collone dans le tableau.
je ne connais pas de fonction prédéfinie qui la donne en Vb, mais on peut "bricoler" avec la gestion d'erreur:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
Private function Numcol(Tableau() as Variant)as integer
On error goto fin
dim i as integer
dim inu as integer
do
   i=i+1
   inu=Lbound(tableau,i)
Loop
fin: Numcol=i-1
End Function

salut [/code]

[Trap D]

J'ai pris ton exemple, pour un programme plus général, il faudrait des connaissances en VB que je n'ai pas.

C'est mon premier programme en VB, il n'y a aucun test de validité dans l'utilisation de la file, à toi de les ajouter !

Je fais afficher le résultat dans une ListBox

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
Rem les tableaux de données
 
Rem contient le nombre de tableaux
Dim nbTab As Integer
 
Dim Tableau(4, 4) As String
 
Rem Index contient le nombre d'élément de chaque tableaux
Dim Index(4) As Integer
 
Rem le tableau des combinaisons
Dim Resultat(1024) As String
 
 
Dim DebFile As Integer
Dim FinFile As Integer
 
Rem marqueur de fin de file
Dim fin As String
 
 
rem initialisation des différentes variables du programme
Private Sub Init()
 
 Tableau(1, 1) = "a"
 Tableau(1, 2) = "b"
 Tableau(2, 1) = "c"
 Tableau(2, 2) = "d"
 Tableau(2, 3) = "e"
 Tableau(3, 1) = "f"
 Tableau(3, 2) = "g"
 Tableau(3, 3) = "h"
 Tableau(4, 1) = "i"
 Tableau(4, 2) = "j"
 
 Index(1) = 2
 Index(2) = 3
 Index(3) = 3
 Index(4) = 2
 
 nbTab = 4
 
 Rem DebFile est le pointeur de début de file
 DebFile = 1
 Rem FinFile est le pointeur de FindeFil
 FinFile = 1
 
 fin = "zzz"
End Sub
 
 
Rem aucune précaution n'est prise, à toi de les ajouter
Sub MetEnFile(str As String)
    Resultat(FinFile) = str
    FinFile = FinFile + 1
    If FinFile > 1024 Then
        MsgBox ("File Pleine")
    End If
 
End Sub
 
Rem aucune précaution n'est prise, à toi de les ajouter
Function Defile() As String
    Defile = Resultat(DebFile)
    DebFile = DebFile + 1
End Function
 
 
Private Sub Command1_Click()
    Dim temp As String
    Dim nouveau As String
 
    Init
 
    Rem initialisation de l'algo
    For i = 1 To Index(1)
        MetEnFile Tableau(1, i)
    Next
    MetEnFile (fin)
 
    Rem l'algo proprement dit
    For i = 2 To nbTab
        temp = Defile()
        While temp <> fin
            For j = 1 To Index(i)
                nouveau = temp + Tableau(i, j)
                MetEnFile nouveau
            Next
            temp = Defile()
        Wend
        MetEnFile fin
    Next
 
    For j = DebFile To FinFile - 2
        List1.AddItem (Defile())
    Next
End Sub

La même chose en Scheme

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
(define (toutes-les-combinaisons lst rest)
  (cond ((null? rest) lst)
        ((null? lst) (toutes-les-combinaisons (map (lambda (x) (list x)) (car rest)) (cdr rest)))
        (else (toutes-les-combinaisons (let g ((x lst))
                                         (if (null? x)
                                             '()
                                             (append (let f ((y (car rest)))
                                                       (if (null? y)
                                                           '()
                                                           (append (list (append (car x) (list (car y))))
                                                                   (f (cdr y)))))
                                                     (g (cdr x)))))
                                       (cdr rest))))) 
 
( toutes-les-combinaisons '() '((a b) (c d e) (f g h)(i j)))

Y'a pas à dire, les langages fonctionnels sont quand même plus concis !!

[HanLee]

Pourquoi est-ce que c'est aussi concis en Scheme ?
Est-ce qu'on pourrait faire la même chose avec C++ avec la STL + Boost éventuellement, avec une taille relativement égale ?

[Trap D]

Je ne connais pas le C++, je suis incapable de te répondre.
Je ne pense cependant pas que ce sera aussi simple en C++ car Scheme gère les listes de façon native, ce qui n'est pas le cas de C++, il faudra écrire toute la machinerie car / cdr append ... (mais c'est peut-être fait après tout )

[juelo]

Pas grand chose à dire à part MERCI beaucoup, que ce soit pour ta solution qui fonctionne à merveille que pour l'interêt que tu as porté à mon pb.

Par contre, j'ai des cours à prendre en algo...

[Trap D]

Tu viens de le comprendre, on ne peut pas programmer si on n'a pas un minimum de connaissance en algo.
Bon courage

[HanLee]

Je ne connais pas le C++, je suis incapable de te répondre.
Je ne pense cependant pas que ce sera aussi simple en C++ car Scheme gère les listes de façon native, ce qui n'est pas le cas de C++, il faudra écrire toute la machinerie car / cdr append ... (mais c'est peut-être fait après tout )

Hum, il y a une librairie qui permet d'utiliser les listes comme dans les langages fonctionnels, par exemple, cons, head, tail, cat (concaténation).
Ca suffit ?

[Trap D]

Peut-être, pose la question sur le forum C++, vraiment, je ne connais strictment rien à C++

[HanLee]

Peut-être, pose la question sur le forum C++, vraiment, je ne connais strictment rien à C++

Oh non j'vais pas poser ma question pour C++ si j'connais les possibilités des bibliothèques . C'est juste que je ne connais pas le Scheme.
Peut être que tu connais la traduction de ton programme en Caml ? (ou bien OCaml)