Combinaisons : Optimisation : Comment simplifier ?

**Gilbert Geyer** · 07/10/2013, 10h34

Bonjour,

J'utilise le code suivant pour obtenir les combinaisons possibles de caractères pris P par P dans une ShortString de N caractères.
Pour l'instant ce code ne fonctionne que pour P <= 9 et fait déjà 145 lignes et pour chaque valeur de P supplémentaire le nombre de lignes requis augmente !!!

Donc je cherche une idée permettant de simplifier ce bourrin.
Je n'ai rien trouvé sur le Net.
J'ai bien essayé de trouver une solution récursive mais j'ai les neurones engluées dans ma logique actuelle.

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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
var SLCombin: tStringList;
 
procedure CombinerPparP(NChar: string; const P: byte);
var LS, i1, i2, i3, i4, i5, i6, i7, i8, lcum: byte; scumd: string;
 
  procedure SuiteR(scum, sr: string);
  var j: byte;
  begin
    for j := 1 to length(sr) do begin
      SLCombin.Add(scum + sr[j]);
    end;
  end;
 
begin
  LS := length(NChar); if LS < P then EXIT;
  if LS = P then begin SLCombin.Add(NChar); EXIT; end;
  for i1 := 1 to LS do begin
    scumd := NChar[i1];
    //sms(scumd);
    case P of
      2: begin
          SuiteR(scumd, Copy(NChar, i1 + 1, LS));
        end;
      3: begin
          lcum := 2;
          SetLength(scumd, lcum);
          for i2 := i1 + 1 to LS do begin
            scumd[lcum] := NChar[i2];
            SuiteR(scumd, copy(NChar, i2 + 1, LS));
          end;
        end;
      4: begin
          lcum := 3;
          SetLength(scumd, lcum);
          for i2 := i1 + 1 to LS do begin
            scumd[lcum - 1] := NChar[i2];
            for i3 := i2 + 1 to LS do begin
              scumd[lcum] := NChar[i3];
              SuiteR(scumd, copy(NChar, i3 + 1, LS));
            end;
          end;
        end;
      5: begin
          lcum := 4;
          SetLength(scumd, lcum);
          for i2 := i1 + 1 to LS do begin
            scumd[lcum - 2] := NChar[i2];
            for i3 := i2 + 1 to LS do begin
              scumd[lcum - 1] := NChar[i3];
              for i4 := i3 + 1 to LS do begin
                scumd[lcum] := NChar[i4];
                SuiteR(scumd, copy(NChar, i4 + 1, LS));
              end;
            end;
          end;
        end;
      6: begin
          lcum := 5;
          SetLength(scumd, lcum);
          for i2 := i1 + 1 to LS do begin
            scumd[lcum - 3] := NChar[i2];
            for i3 := i2 + 1 to LS do begin
              scumd[lcum - 2] := NChar[i3];
              for i4 := i3 + 1 to LS do begin
                scumd[lcum - 1] := NChar[i4];
                for i5 := i4 + 1 to LS do begin
                  scumd[lcum] := NChar[i5];
                  SuiteR(scumd, copy(NChar, i5 + 1, LS));
                end;
              end;
            end;
          end;
        end;
      7: begin
          lcum := 6;
          SetLength(scumd, lcum);
          for i2 := i1 + 1 to LS do begin
            scumd[lcum - 4] := NChar[i2];
            for i3 := i2 + 1 to LS do begin
              scumd[lcum - 3] := NChar[i3];
              for i4 := i3 + 1 to LS do begin
                scumd[lcum - 2] := NChar[i4];
                for i5 := i4 + 1 to LS do begin
                  scumd[lcum - 1] := NChar[i5];
                  for i6 := i5 + 1 to LS do begin
                    scumd[lcum] := NChar[i6];
                    SuiteR(scumd, copy(NChar, i6 + 1, LS));
                  end;
                end;
              end;
            end;
          end;
        end; // 7
      8: begin
          lcum := 7;
          SetLength(scumd, lcum);
          for i2 := i1 + 1 to LS do begin
            scumd[lcum - 5] := NChar[i2];
            for i3 := i2 + 1 to LS do begin
              scumd[lcum - 4] := NChar[i3];
              for i4 := i3 + 1 to LS do begin
                scumd[lcum - 3] := NChar[i4];
                for i5 := i4 + 1 to LS do begin
                  scumd[lcum - 2] := NChar[i5];
                  for i6 := i5 + 1 to LS do begin
                    scumd[lcum - 1] := NChar[i6];
                    for i7 := i6 + 1 to LS do begin
                      scumd[lcum] := NChar[i7];
                      SuiteR(scumd, copy(NChar, i7 + 1, LS));
                    end;
                  end;
                end;
              end;
            end;
          end;
        end; // 8
      9: begin
          lcum := 8;
          SetLength(scumd, lcum);
          for i2 := i1 + 1 to LS do begin
            scumd[lcum - 6] := NChar[i2];
            for i3 := i2 + 1 to LS do begin
              scumd[lcum - 5] := NChar[i3];
              for i4 := i3 + 1 to LS do begin
                scumd[lcum - 4] := NChar[i4];
                for i5 := i4 + 1 to LS do begin
                  scumd[lcum - 3] := NChar[i5];
                  for i6 := i5 + 1 to LS do begin
                    scumd[lcum - 2] := NChar[i6];
                    for i7 := i6 + 1 to LS do begin
                      scumd[lcum - 1] := NChar[i7];
                      for i8 := i7 + 1 to LS do begin
                        scumd[lcum] := NChar[i8];
                        SuiteR(scumd, copy(NChar, i8 + 1, LS));
                      end;
                    end;
                  end;
                end;
              end;
            end;
          end;
        end; // 9
    end; // case
  end; // for i
end; // CombinPparP

Pour utiliser :

Code :

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

1
2
3
4
5
6
7
8
9
procedure TForm1.iCombinPparPClick(Sender: TObject);
begin
  SLCombin := tStringList.create;
  SLCombin.Sorted := true; SLCombin.Duplicates := dupIgnore;
  CombinerPparP('123456789AB', 8);
  RichEdit1.Lines.AddStrings(SLCombin);
  RichEdit1.Lines.add('Nb = ' + intToStr(SLCombin.Count));
  SLCombin.Free;
end;

Merci par avance pour toute idée.

A+.

**ShaiLeTroll** · 07/10/2013, 11h06

les combinaisons possibles de caractères pris P par P dans une ShortString de N caractères.

Le nombre de combinaisons va être tellement important qu'il va dépasser la capacité mémoire !

On a déjà écrit ce genre d'algo sur le forum !
Test possibilités possible longue boucle
Algorithme de combinaisons , le plus proche serait GetArrangementAvecRepetition mais toi il te faudrait un GetArrangementSansRepetition !

**Gilbert Geyer** · 07/10/2013, 11h50

Re-bonjour,

Merci ShaiLeTroll

Le nombre de combinaisons va être tellement important qu'il va dépasser la capacité mémoire !

... En fait je n'ai pas le besoin d'aller plus que loin que P = 64 max voire même seulement P = 49 Max.

On a déjà écrit ce genre d'algo sur le forum !
Test possibilités possible longue boucle

... "Test possibilités possible longue boucle" : je sais j'y avais participé mais il s'agissait en réalité de sortir les Anagrammes. En plus les Anagrammes c'est des permutations dont le nombre des possibles est nettement plus important.

Algorithme de combinaisons , le plus proche serait GetArrangementAvecRepetition mais toi il te faudrait un GetArrangementSansRepetition !

... Exact. Mais dommage que le code de GetArrangementAvecRepetition soit du C++ sinon je l'aurais utilisé pour récupérer les Arrangements dans une Stringlist avec DupIgnore.

A+.

**ShaiLeTroll** · 07/10/2013, 11h53

Ton algo fourni 330 cela correspond au "Combinaisons sans répétition"
La formule c'est n! / (n - k)! / k!
Donc 11! / 7! / 4! = 11 * 10 * 9 * 8 / (4 * 3 * 2) = 7920 / 24 = 330

J'ai deux boucles
La première dans CombinerPparP2 qui élimine un objet dans NChar
La seconde dans SuiteR qui cherche les combinaisons dans NChar en conservant l'ordre
Comme CombinerPparP2 fourni une sorte de rotation de NChar, SuiteR génère autant de suite que nécessaire

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
 
procedure CombinerPparP2(NChar: string; const P: byte);
 
  procedure SuiteR(scum, sr: string; const P: byte);
  var
    j: Integer;
  begin
    if Length(sr) > 0 then
    begin
      scum := scum + sr[1];
      if Length(scum) < P then
      begin
        for j := 2 to length(sr) do
          SuiteR(scum, Copy(sr, j, MaxInt), P);
      end
      else
        SLCombin.Add(scum);
    end;
  end;
 
var
  LS: Integer;
  j: integer;
begin
  LS := length(NChar);
  if LS < P then
    exit;
  if LS = P then
  begin
    SLCombin.Add(NChar);
    exit;
  end;
 
  for j := 1 to length(NChar) do
  begin
    SuiteR('', NChar, P);
    NChar := Copy(NChar, 2, MaxInt);
  end;
end;

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
procedure TForm1.Button1Click(Sender: TObject);
begin
  SLCombin := tStringList.create;
  //SLCombin.Sorted := true;
  //SLCombin.Duplicates := dupIgnore;
 
  CombinerPparP('123456789AB', 4);
  Memo1.Lines.AddStrings(SLCombin);
  Memo1.Lines.add('Nb = ' + intToStr(SLCombin.Count));
 
  SLCombin.Clear();
 
  CombinerPparP2('123456789AB', 4);
  Memo1.Lines.AddStrings(SLCombin);
  Memo1.Lines.add('Nb = ' + intToStr(SLCombin.Count));
 
  SLCombin.Free;
end

;

**Gilbert Geyer** · 07/10/2013, 12h44

Re-Bonjour ShaiLeTroll,

Ton algo fourni 330 cela correspond au "Combinaisons sans répétition"
La formule c'est n! / (n - k)! / k!
Donc 11! / 7! / 4! = 11 * 10 * 9 * 8 / (4 * 3 * 2) = 7920 / 24 = 330

Absolument d'accord.

CombinerPparP2 : J'ai deux boucles
La première dans CombinerPparP2 qui élimine un objet dans NChar
La seconde dans SuiteR qui cherche les combinaisons dans NChar en conservant l'ordre
Comme CombinerPparP2 fourni une sorte de rotation de NChar, SuiteR génère autant de suite que nécessaire

OK merci pour les explications.
J'ai vite testé et comparé les résultats pour P <= 9 avec ceux de mon bourrin et les résultats sont les mêmes.
Mille fois merci t'es un chef

Et vu ta rapidité je suis admiratif car j'ai galéré en essayant de simplifier.

A+.

Combinaisons : Optimisation : Comment simplifier ?

Langage Delphi

Discussions similaires

Partager

Partager