Discussion :

[tom_tom73]

Bonjour,

Je dois créer un programme qui effectue toutes les comparaisons possibles des n premiers entiers.

EX : pour n=3 je dois avoir 6 comparaisons :

[123][213][231][312][132][321]

J'ai une procedure qui effectue un trie à bulle mais je n'arrive pas à afficher toutes les comparaisons.

Voici le 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
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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
 
program TriePermutation;
 
uses SysUtils, Windows;
 
CONST MAX_ELT = 10000;
 
VAR TDebut, TFin : Longword; // Variables Globales, TempsDébut et TempsFin en ms
    NbComp       : integer;
 
TYPE TabInt = Array [ 1..MAX_ELT ] OF integer;
 
Procedure InitTabInt ( VAR leTabInt : TabInt; NbElts : integer );
// Initialise le tableau, TabInt, du nbr d'éléments, NbElts
VAR i, j : integer;
begin
  j := 0;
  for i:= NbElts DOWNTO 1 DO
    begin
      j := j + 1;
      leTabInt [ j ] := i;
    end;
end;
 
Procedure AfficherTableau ( leTabInt : TabInt; NbElts : integer );
// Affiche le tableau, leTabInt
VAR i : integer;
Begin
  Write ( '[' );
  FOR i := 1 TO NbElts DO Write ( leTabInt [ i ] : 3 );
  Write ( '  ]' );
End;
 
Procedure TrieBulle ( VAR leTabInt : TabInt; NbElts : integer );
// Trie le tableau, leTabInt, façon Trie à Bulle
VAR i, j, aux : integer;
begin
  NbComp := -1;
  TDebut := gettickCount();
  AfficherTableau ( leTabInt, NbElts );
  Writeln;
  FOR i := 1 TO NbElts DO Begin
    FOR j := NbElts DOWNTO i DO Begin
      IF ( leTabInt [ j - 1 ] > leTabInt [ j ] ) THEN
      Begin
        aux := leTabInt [ j - 1 ];
        leTabInt [ j - 1 ] := leTabInt [ j ];
        leTabInt [ j ] := aux;
        // Affiche le tableau, leTabInt
        AfficherTableau ( leTabInt, NbElts );
        Writeln;
      end;
    end;
  end;
  TFin := gettickCount();
end;
 
VAR i, LE_MAX_ELTS : integer;
    unTabInt       : TabInt;
    TempsExec      : Longword;
Begin
  Writeln;
  Writeln('                  ²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²                  ');
  Writeln('                  ²                                      ²                  ');
  Writeln('                  ²  EX ALGO -- TRIE ET PERMUTATIONS --  ²                  ');
  Writeln('                  ²                                      ²                  ');
  Writeln('                  ²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²²                  ');
  Writeln;
  Writeln;
  Writeln ( '--> Saisir le nombre d elements du tableau, >1 et MAX=10 000 :' );
  Readln ( LE_MAX_ELTS );
 
  While (( LE_MAX_ELTS <= 1 ) OR ( LE_MAX_ELTS > MAX_ELT )) DO Begin
    Writeln;
    Writeln ( '--> Saisir le nombre d elements du tableau, >1 et MAX=10 000 :' );
    Readln ( LE_MAX_ELTS );
  end;
 
  // Initialisation du tableau, unTabInt
  InitTabInt ( unTabInt, LE_MAX_ELTS );
 
  Writeln;
  Writeln ( '² Votre Tableau : ²' );
  Writeln;
  // Affiche le tableau, leTabInt
  AfficherTableau( unTabInt, LE_MAX_ELTS );
 
  Writeln;
  Writeln;
  Writeln ( '² Comparaisons : ²' );
  Writeln;
 
  // Trie le tableau, leTabInt, façon Trie à Bulle
  TrieBulle ( unTabInt, LE_MAX_ELTS );
 
  Writeln;
  Writeln;
  Writeln ( '² Nombre de Comparaisons : ²' );
  Writeln;
  Writeln('Le nombre de comparaisons est de : ', NbComp);
 
  Writeln;
  Writeln;
  Writeln ( '² Temps Execution : ²' );
  Writeln;
 
  TempsExec := TFin-TDebut;
 
  Writeln('Le temps d execution du trie a bulle est de : ');
  Writeln;
  Writeln('[ ', TempsExec, ' ms ] soit donc [ ', formatfloat('0.00', TempsExec/1000),' sec ]');
 
  Writeln;
  Writeln;
  Writeln ( 'Fin' );
  Readln;
end.

Ce code fonctionne mais ne m'afficher pas toutes les comparaisons.
Ex pour n=3, il m'affiche:



J'attends votre aide...

Merci beaucoup

[Dr.Who]

nombres de permutation = factorielle de longueur tableau

soit (longueur = permutations totales (~taille de [ 1, 2, n ]) :

1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5 040 (~120Ko)
8! = 40 320 (~1Mo)
9! = 362 880 (~10Mo)
10! = 3 628 800 (~119Mo)
11! = 39 916 800 {~1,4Go}
12! = 479 001 600
13! = 6 227 020 800


donc la longueur du tableau ne doit pas dépasser au maximum 7 éléments dans un programme console à affichage des permutations en direct.
aprés, on peut au maximum monter à 8, 9 avec inscription des permutations dans un fichier texte ou plus mais avec plusieurs fichiers texte.

[Dr.Who]

permutations :

cas pour L=2 :

-> [1,2]
permuter 0 et 1 -> [2,1]

répéter L fois :

permuter 0 et 1->[1,2]

cas pour L=3 :

-> [1,2,3]
permuter 0 et L-1 -> [3,2,1]

répéter L fois :

permuter 0 et 2 -> [1,2,3]
permuter 1 et 2 -> [1,3,2]

cas pour L=4 :

-> [1,2,3,4]
permuter 0 et L-1 -> [4,2,3,1]

répéter L fois :

permuter 0 et 3 -> [1,2,3,4]
permuter 2 et 3 -> [1,2,4,3]
permuter 1 et 3 -> [1,3,4,2]
permuter 2 et 3 -> [1,3,2,4]
permuter 1 et 3 -> [1,4,2,3]
permuter 2 et 3 -> [1,4,3,2]

[Montor]

la réponse est ici http://www.developpez.net/forums/d73...bleau-colonne/

[Dr.Who]

la réponse est ici http://www.developpez.net/forums/d73...bleau-colonne/

mmm pas vraiment, ici il s'agit de permutation et non d'un tri de n'importe qu'elle sorte.

comme je l'ai expliqué, les permutations sont des factorielles et donc elle sont limitée en nombre d'éléments par la capacité en memoire et du disque de la machine.

faire un algo de permutation n'est pas compliqué en soit, mais ne peu aller plus loin qu'un certain petit nombre.
en gros, vouloir toute les permutations d'un coups à au dela de 7 ou 8 éléments devient quasiment ingérable...

seul une permutation "virtuelle" pas à pas pourrait correspondre, mais encore ici, il serait fastidieux de cliquer plus de 100 fois sur un bouton pour avoir toute les permutations possible pour 5 elements.

de toute façon, a partir du moment ou l'on commence à avoir des choses qui augmente de façon exponentiel ou factorielle ... il faut s'attendre à ne pas pouvoir aller trés loin, on se trouve vite limité par les machines et également par nos minces capacité à pouvoir lire un document comportant plusieurs millions ou plusieurs milliards de valeurs, ce qui au passage serait inutile et n'apporterait rien de plus.