Discussion :

[djbebop]

Bonjour a tous,

premier message donc desolé si je m'y prends un peu mal

cela fait une semaine que je m'enerve sur un programme pascal a faire en plus assez simple : je m'explique : l'utilisateur doit entrer 20 nombres.Le but de l'exo est d'afficher toutes les combinaisons à 6 chiffres possibles parmis les 20 nombres entrés par l'utilisateur.De plus il ne faut pas que le meme chiffre apparaissent la meme fois.Enfin l'ordre n'a pas d'importance.

Exemple : utilisateur : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
resultat: 4 5 6 7 8 10, 9 20 12 2 3 4 etc...

voila mon programme :

Code Delphi :

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
PROGRAM exo;
VAR a,b,c,d,e,f:integer;
    cpt1,cpt2,cpt3,cpt4,cpt5,cpt6:integer;
    i,n:integer;
TYPE t=array[1..20] of integer;
 
BEGIN                 {programme principal}
     write('merci d''entrer les vingts chiffres');
     for i:=1 to 20 do begin read(n);
						t[i]:=n;
						end;
 
     a:=t[1];b:=[2];c:=t[3];d:=t[4];e:=t[5];f:=t[6];
     while (cpt1<>20) do
     if (a<>b) and (a<>c) and (a<>d) and (a<>e) and (a<>f)
     then while (cpt2<>20) do
          if (b<>a) and (b<>c) and (b<>d) and (b<>e) and (b<>f)
          then while (cpt3<>20) do
               if (c<>a) and (c<>b) and (c<>d) and (c<>e) and (c<>f)
               then while (cpt4<>20) do
                    if (d<>a) and (d<>b) and (d<>c) and (d<>e) and (d<>f)
                    then
                        while (cpt5<>20) do
                         if  (e<>a) and (e<>b) and (e<>c) and (e<>d) and (e<>f)
                         then
				while (cpt6<>20) do
                              if (f<>a) and (f<>b) and (f<>c) and (f<>d) and (f<>e)
                              then begin writeln(a,' -',b,'- ',c,'- ',d,'- ',e,'- ',f)
                                   cpt6:=cpt6+1;
                                   f:=t[cpt6];
					               end
                              else begin cpt6:=cpt6+1;
                                   f:=t[cpt6];
					               end
                              else begin cpt5:=cpt5+1;
                                         e:=t[cpt5];
                                   end
 
                          else begin
                               cpt4:=cpt4+1;
                                d:=t[cpt4];
                               end
                   else begin
                     cpt3:=cpt3+1;
                     c:=t[cpt3];
                        end
               else begin
                cpt2:=cpt2+1;
                b:=t[cpt2];
                    end
           else begin
        cpt1:=cpt1+1;
        a:=t[cpt1];
                end ;
 
 readln;
 readln;
 
END.

Merci de votre aide la plus rapide possible !

bebop

[Loceka]

D'abord essaye de résoudre un problème similaire mais plus petit.
Par exemple, intéresse-toi à l'ensemble des combinaisons de 2 (ou 3) éléments possibles à partir d'un ensemble de 6 éléments.

Ca donne ça, normalement :

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
4 5 6 7 8 9
 
4 5
4 6
4 7
4 8
4 9
 
5 6
5 7
5 8
5 9
 
6 7
6 8
6 9
 
7 8
7 9
 
8 9
____________
4 5 6 7 8 9
 
4 5 6
4 5 7
4 5 8
4 5 9
 
4 6 7
4 6 8
4 6 9
 
4 7 8
4 7 9
 
4 8 9
 
5 6 7
5 6 8
5 6 9
 
5 7 8
5 7 9
 
5 8 9
 
6 7 8
6 7 9
 
6 8 9
 
7 8 9

A partir de là, essaye de voir comment les obtenir à l'aide de boucles imbriquées (si tu le fais au cas par cas, il devrait te falloir autant de boucles que tu as d'éléments dans tes combinaisons, soit 6 boucles dans ton cas).

Maintenant, si tu veux une solution plus générale, qui puisse te donner toutes les combinaisons à 'n' éléments à partir d'un ensemble à 'N' éléments, je te conseille d'utiliser un tableau intermédiaire - de taille 'n' - correspondant à la combinaison que tu es en train de traiter.
Normalement cette solution ne nécessite que 2 boucles (si je ne me suis pas trompé dans mon algo ^^), par contre elle est beaucoup moins intuitive que l'autre.

[pseudocode]

Normalement cette solution ne nécessite que 2 boucles (si je ne me suis pas trompé dans mon algo ^^)

tout a fait, 2 boucles suffisent.

par contre elle est beaucoup moins intuitive que l'autre.

Question de point de vue. Par exemple, pour un choix de 3 elements parmis 10, Il suffit d'envisager le probleme comme un compteur kilometrique à 3 chiffres: le compteur peut aller de 000 a 999. Chaque chiffre donne le n° de l'element a prendre.

Dans notre cas, pour respecter les contraintes, il faut prendre en compte seulement les valeurs du compteur qui contiennent des chiffres differents (pas de doublon d'element) et classés de maniere croissante (pas de doublon de sequence).

[Jedai]

Maintenant, si tu veux une solution plus générale, qui puisse te donner toutes les combinaisons à 'n' éléments à partir d'un ensemble à 'N' éléments, je te conseille d'utiliser un tableau intermédiaire - de taille 'n' - correspondant à la combinaison que tu es en train de traiter.
Normalement cette solution ne nécessite que 2 boucles (si je ne me suis pas trompé dans mon algo ^^), par contre elle est beaucoup moins intuitive que l'autre.

Tu peux également faire de la récursion, c'est plus intuitif que la solution avec le tableau, et probablement un peu moins efficace (mais de façon insignifiante, sauf si tu travailles vraiment sur de très gros ensembles de données, et le gain en lisibilité peut compenser selon l'application).

--
Jedaï

[pseudocode]

Tu peux également faire de la récursion, c'est plus intuitif que la solution avec le tableau, et probablement un peu moins efficace (mais de façon insignifiante, sauf si tu travailles vraiment sur de très gros ensembles de données, et le gain en lisibilité peut compenser selon l'application).

mdr. Je me suis retenu d'ecrire un message du genre "si Jedai etait la, il résoudrait ton probleme avec 1 ligne de Haskell".

Bon, ceci dit, je suppose qu'il vaut mieux rester dans le non recursif pour un premier algo de combinatoire en Pascal.

[alex_pi]

Question de point de vue. Par exemple, pour un choix de 3 elements parmis 10, Il suffit d'envisager le probleme comme un compteur kilometrique à 3 chiffres: le compteur peut aller de 000 a 999. Chaque chiffre donne le n° de l'element a prendre.

Je rappel qu'il fait un tirage non ordonné et sans remise, ce n'est donc pas ça :-)

[millie]

Je rappelle les liens données par Jean-Marc :

Generating all $n$-tuples: http://www-cs-faculty.stanford.edu/~knuth/fasc2a.ps.gz
Generating all permutations: http://www-cs-faculty.stanford.edu/~knuth/fasc2b.ps.gz
Generating all combinations: http://www-cs-faculty.stanford.edu/~knuth/fasc3a.ps.gz
Generating all partitions: http://www-cs-faculty.stanford.edu/~knuth/fasc3b.ps.gz
Generating all trees: http://www-cs-faculty.stanford.edu/~knuth/fasc4a.ps.gz
History of Combinatorial Generation: http://www-cs-faculty.stanford.edu/~knuth/fasc4b.ps.gz

Ton problème correspond (il me semble) à la génération de toutes les partitions de taille 6.

[pseudocode]

Je rappel qu'il fait un tirage non ordonné et sans remise, ce n'est donc pas ça :-)

sans remise, c'est sur. Non ordonné c'est moins clair. Le PO dit "l'ordre n'a pas d'importance"... ca peu sous entendre l'un comme l'autre.

De plus j'ai rajouté des contraintes sur mon analogie de compteur kilometrique.

Code java :

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

1
2
3
4
5
6
7
8
9
10
11
 
/* partitions de taille 3 parmis 6 elelments */
 
// liste (sans doublons)
int[] liste = new int[] {4,5,6,7,8,9};
 
// compteur de 000 a XXX, sans doublons de chiffre/sequence
for(int a=0;a<liste.length;a++)
    for(int b=a+1;b<liste.length;b++)
        for(int c=b+1;c<liste.length;c++)
            System.out.println(liste[a]+","+liste[b]+","+liste[c]);

donne bien le résultat donné par Loceka

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
4,5,6
4,5,7
4,5,8
4,5,9
4,6,7
4,6,8
4,6,9
4,7,8
4,7,9
4,8,9
5,6,7
5,6,8
5,6,9
5,7,8
5,7,9
5,8,9
6,7,8
6,7,9
6,8,9
7,8,9

[Loceka]

Bon, ceci dit, je suppose qu'il vaut mieux rester dans le non recursif pour un premier algo de combinatoire en Pascal.

C'est aussi ce que je me suis dit, et puis c'est tellement plus marrant de se creuser la tête pour le faire en itératif. (remarque que je viens d'essayer de le faire en récursif et c'est pas si évident que ça non plus, mais je suis un peu rouillé)

[Jedai]

C'est aussi ce que je me suis dit, et puis c'est tellement plus marrant de se creuser la tête pour le faire en itératif. (remarque que je viens d'essayer de le faire en récursif et c'est pas si évident que ça non plus, mais je suis un peu rouillé)

Je ne suis pas expert Pascal, je vais faire ça en pseudo-code :

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
combinaison(n, elements)
   comb := alloue n cases
   aux_combi(0, n, comb, elements)
fin
 
aux_combi(limite, reste, debut, elements)
   si reste == 0
   alors
      affiche comb[]
      retour
   finsi
 
   pour i=limite à (taille(elements)- reste - 1)
      debut[taille(comb) - reste] := elements[i]
      aux_combi(i+1, reste-1, debut, elements)
   finpour
fin

Bien sûr codé comme ça, ça sera sûrement très lent... J'avais oublié à quel point l'absence de closures (ou d'une fonctionnalité plus ou moins équivalente, style objet) rend pénible la mise en oeuvre de récursions efficaces sans recourir à d'inélégantes (et peu réentrantes) variables globales.

Dans un langage plus adapté, l'approche récursive est par contre immédiate :

Code Haskell :

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

1
2
combination 0 _ = [[]]
combination n xs = [e:es| e:ys <- tails xs, es <- combination (n-1) ys]

--
Jedaï

[NowadaysOrLater]

Bonjour,

J'ai eu la même problématique, générer une combinaison de n éléments parmi N.

Voici mes propositions en C# (avec un type générique)

Non récursif

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
 
        public static List<List<T>> NonRecursiveGetCombination(List<T> initialList, int nbElements)
        {
            //Initializations
            // the list of the different combinations
            List<List<T>> result = new List<List<T>>();
            int listLength = initialList.Count;
            bool hasOneMoved;
 
 
            // if the list is smaller than the number of element in one combination return an empty list
            if (nbElements > listLength) return result;
 
            // initialize the cursors
            int[] cursors = new int[nbElements];
            for (int i = 0; i < nbElements; i++)
            {
                cursors[i] = i;
            }
 
            //infinite loop : will end when all combinations are found
            for (; ; )
            {
                // new combination
                List<T> currentCombination = new List<T>();
                // set the elements
                for (int currentCursor = 0; currentCursor < nbElements; currentCursor++)
                {
                    currentCombination.Add(initialList[cursors[currentCursor]]);
                }
                // add it to the result
                result.Add(currentCombination);
 
                hasOneMoved = false;
                // get to the next combination
                for (int currentCursor = nbElements - 1; currentCursor >= 0; currentCursor--)
                {
                    // if the current cursor do not point on the last element
                    if (cursors[currentCursor] != (listLength - 1))
                    {
                        /* if the current cursor has a following cursor  
                         * i.e. current cursor's id is stricly inferior to nbElements -1
                         */
                        if (currentCursor < (nbElements - 1))
                        {
                            // and finally if the next 'box' is not occupied
                            if (cursors[currentCursor + 1] != cursors[currentCursor] + 1)
                            {
                                //then the current cursor goes to the next 'box'
                                cursors[currentCursor]++;
                                //and every following cursors follow
                                for (int i = currentCursor; i < nbElements -1; i++)
                                {
                                    cursors[i + 1] = cursors[i]+1;
                                }
 
                                hasOneMoved = true;
                                break;
                            }
                        }
                        else // the last cursor
                        {
                            // if not on the 'last box' 
                            if (cursors[currentCursor] != (listLength - 1))
                            {
                                // goes to the next "box"
                                cursors[currentCursor]++;
                                hasOneMoved = true;
                                break;
                            }
                        }
                    }
                }
                // if none can be moved then it means the function is over
                if (!hasOneMoved) break;
            }
            return result;
        }

Récursif

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
public static List<List<T>> RecursiveGetCombinations(List<T> initialList, int nbElements)
        {
            List<List<T>> result = new List<List<T>>();
            // if the list is smaller than the number of element in one combination return an empty list
            if (nbElements > initialList.Count) return result;
 
            // if combination of one element then return a list of one element list
            if (nbElements == 1)
            {
                foreach (T item in initialList)
                {
                    List<T> tmp = new List<T>();
                    tmp.Add(item);
                    result.Add(tmp);
                }
            }
            /* here we need to create a duplication of
             * the initial list to avoid changing the initial list
            */
            List<T> tmpList = new List<T>(initialList);
 
            // for each element
            foreach (T item in initialList)
            {
                // the current item is appart
                tmpList.Remove(item);
                // get the sub combinations of n-1 elements
                List<List<T>> tmpReceptacle = RecursiveGetCombinations(tmpList, nbElements - 1);
                // build the result from the current element and the sub combinations and add it to the result
                foreach (List<T> listSub in tmpReceptacle)
                {
                    List<T> tmpListToAvoidchange = new List<T>(listSub);
                    tmpListToAvoidchange.Add(item);
                    result.Add(tmpListToAvoidchange);
                }
            }
            return (result);
        }