Rotation "circulaire" d'un tableau 2D

**BeanzMaster** · 22/03/2020, 12h57

Salut à tous, je recherche une solution efficace pour effectuer une rotation "circulaire" de k éléments vers la droite ou vers la gauche des valeurs d'un tableau 2D de dimension impaire de NxN, car j'ai de la peine à mettre un algorithme efficace en place.

Exemples :

Avec un tableau de 3x3

Original :
[1, 2, 3]
[4, 5, 6]
[7, 8, 9]

Sortie avec K=1:
[4, 1, 2]
[7, 5, 3]
[8, 9, 6]

Sortie avec K=2:
[7, 4, 1]
[8, 5, 2]
[9, 6, 3]

Avec un tableau de 5x5

Original :
[01, 02, 03, 04, 05]
[06, 07, 08, 09, 10]
[11, 12, 13, 14, 15]
[16, 17, 18, 19, 20]
[21, 22, 23, 24, 25]

Sortie avec K=1:
[06, 01, 02, 03, 04]
[11, 12, 07, 08, 05]
[16, 17, 13, 09, 10]
[21, 18, 19, 14, 15]
[22, 23, 24, 25, 20]

Merci d'avance pour votre aide

PS : Mes tableaux de base sont des tableaux 1D déclarés ainsi

Code :

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

1
2
3
4
5
6
 
Type
  Mat3x3 : array [0..8] of Single;   //3x3
  Mat5x5 : array [0..24] of Single; //5x5
  Mat7x7 : array [0..48] of Single; //7x7
  MatNxN : Array of single; //NxN

A+

Jérôme

**tourlourou** · 22/03/2020, 13h48

Bonjour Jérôme,
Ton besoin fera-t-il appel à de gros volumes et avec une exigence de rapidité ?
La taille sera-t-elle quelconque, quand les calculs se présenteront, ou par séries de taille homogène ? Et pareil pour le décalage.
Tes tableaux 1D sont-ils dans l'ordre des lignes ou des colonnes ?
Je pense à un objet dont une méthode permettrait de précalculer les matrices d'indices, mais cela pose 2 problèmes : celui du calcul des indices (thx, captain obvious !) et celui du stockage des matrices déjà calculées pour N et k.
Quand > 3, la rotation de toutes les sous-matrices est de k ?

**BeanzMaster** · 22/03/2020, 14h43

Bonjour

Envoyé par tourlourou

Bonjour Jérôme,
Ton besoin fera-t-il appel à de gros volumes et avec une exigence de rapidité ?
La taille sera-t-elle quelconque, quand les calculs se présenteront, ou par séries de taille homogène ? Et pareil pour le décalage.

Gros volume non c'est pour des matrices de convolution, max 7x7 pour l'instant, rapide oui.

Envoyé par tourlourou

Tes tableaux 1D sont-ils dans l'ordre des lignes ou des colonnes ?

LignexColonne

[ 1,2,3,
4,5,6
7,8,9 ]

Envoyé par tourlourou

Je pense à un objet dont une méthode permettrait de précalculer les matrices d'indices, mais cela pose 2 problèmes : celui du calcul des indices (thx, captain obvious !) et celui du stockage des matrices déjà calculées pour N et k.

Je préfèrais éviter les tables précalculées.

Envoyé par tourlourou

Quand > 3, la rotation de toutes les sous-matrices est de k ?

Oui
J'ai trouvé ça et tenté de convertir en

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
procedure TForm1.CircularShiftLeft(var mat : TArray3x3);
Var
  row, col, m, n, i, j : Integer;
  prev, curr : Integer;
begin
  (*
  row - Staring row index
  m - ending row index
  col - starting column index
  n - ending column index
  i - iterator
  *)
  row := 0;
  col := 0;
  m := 3;
  n := 3;
  while ((row < m) and (col < n)) do
  begin
 
     // if ( ((row + 1) = m) or ((col + 1) = n)) then break;
 
      // Store the first element of next
      // row, this element will replace
      // first element of current row
      prev := mat[(row + 1) * 3 + col];
 
      // Move elements of first row
      // from the remaining rows
      for i := col to (n-1) do
      begin
        curr := mat[row * 3 + i];
        mat[row * 3 + i] := prev;
        prev := curr;
      end;
      Inc(row);
 
      // Move elements of last column
      // from the remaining columns
      for i := row to (m-1) do
      begin
        curr := mat[i * 3 + (n-1)];
        mat[i * 3 + (n-1)] := prev;
        prev := curr;
      end;
      Dec(n);
 
      // Move elements of last row
      // from the remaining rows
      if (row < m) then
      begin
        for i := Col Downto (n-1) do
        begin
          curr := mat[(m-1) * 3 + i];
          mat[(m-1) * 3 + i] := prev;
          prev := curr;
        end;
     end;
     Dec(m);
 
    // Move elements of first column
    // from the remaining rows
    if (col < n) then
    begin
      for i := row downto m-1 do
      begin
        curr := mat[i * 3 + col];
        mat[i * 3 + col] := prev;
        prev := curr;
      end;
    end;
    Inc(col);
  end;
end;

Mais cela ne me donne pas le résultat voulu

Entrée :
[1, 2, 3]
[4, 5, 6]
[7, 8, 9]

Sortie :
[4, 1, 2]
[9, 8, 3]
[7, 8, 6]

**BeanzMaster** · 22/03/2020, 15h04

Bon j'ai corrigé l'erreur

Code :

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

1
2
3
4
5
6
7
8
9
10
11
  // Move elements of last row
  // from the remaining rows
  if (row < m) then
  begin
    for i := (n-1) downto Col do
    begin
      curr := mat[(m-1) * 3 + i];
      mat[(m-1) * 3 + i] := prev;
      prev := curr;
    end;
  end;

Cela semble fonctionner, me reste à ajouter le nombre de fois et faire la même chose dans le sens anti-horaire

**BeanzMaster** · 22/03/2020, 18h51

Bon ben je galère un peu cela fonctionne bien avec des tableaux 3x3 mais pas avec des tableaux 5x5 et supérieur. Je vais réécrire cette fonction. Il semble y avoir un problème avec le calcul des indices row/col et n/m

**Roland Chastain** · 22/03/2020, 19h22

Bonsoir Jérôme !

Moi je ferais quelque chose comme ça :

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
type
  Mat3x3 = array [0..8] of Single;
 
procedure RotateRight(var AMat3x3: Mat3x3);
const
  COriginalIndex: array [0..8] of integer = (
    3, 0, 1,
    6, 4, 2,
    7, 8, 5
  );
var
  i: integer;
  result: Mat3x3;
begin
  for i := Low(Mat3x3) to High(Mat3x3) do
    result[i] := AMat3x3[COriginalIndex[i]];
  AMat3x3 := result;
end;
 
procedure WriteMat3x3(const AMat3x3: Mat3x3);
begin
  WriteLn(
    AMat3x3[0], AMat3x3[1], AMat3x3[2], LineEnding,
    AMat3x3[3], AMat3x3[4], AMat3x3[5], LineEnding,
    AMat3x3[6], AMat3x3[7], AMat3x3[8]
  );
end;
 
var
  m: Mat3x3;
  i: integer;
 
begin
  for i := Low(Mat3x3) to High(Mat3x3) do
    m[i] := i;
  WriteMat3x3(m);
  RotateRight(m);
  WriteMat3x3(m);
end.

Je crois comprendre que c'est ce que tu voulais éviter mais pour ma part je ne vois pas de meilleure solution.

**BeanzMaster** · 22/03/2020, 20h12

Salut et merci Roland, j'ai repris ma copie voici le code fonctionnel

Pour tester créez une nouvelle appli avec 3 TButton, 2 TMemo et 1 TSpinEdit

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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
unit Unit1;
 
{$mode objfpc}{$H+}
 
interface
 
uses
  Classes, SysUtils, Forms, Controls, Graphics, Dialogs, StdCtrls, Spin;
 
Const
  cTabSize = 5; //5 //7
 
type
 
  TMyArray = array[0..((cTabSize * cTabSize) - 1)] of Integer;
 
  { TForm1 }
 
  TForm1 = class(TForm)
    Memo1 : TMemo;
    Memo2 : TMemo;
    Button1 : TButton;
    Button2 : TButton;
    speDecalage : TSpinEdit;
    Label1 : TLabel;
    Reset : TButton;
    procedure FormCreate(Sender : TObject);
    procedure FormShow(Sender : TObject);
    procedure Button1Click(Sender : TObject);
    procedure Button2Click(Sender : TObject);
    procedure ResetClick(Sender : TObject);
  private
 
  public
    AnArray : TMyArray;
    procedure CircularShiftLeft(var mat : TMyArray; k : Byte);
    procedure CircularShiftRight(var mat : TMyArray; k : Byte);
    procedure PrintArray(arr : TMyArray; aMemo : TMemo);
    procedure ResetTab;
  end;
 
var
  Form1 : TForm1;
 
implementation
 
{$R *.lfm}
 
{ TForm1 }
 
procedure TForm1.FormCreate(Sender : TObject);
begin
  ResetTab;
  Memo2.Clear;
  Memo1.Clear;
  speDecalage.MaxValue := (cTabSize-1) * 4;
end;
 
procedure TForm1.FormShow(Sender : TObject);
begin
  PrintArray(AnArray, Memo1);
end;
 
procedure TForm1.Button1Click(Sender : TObject);
begin
  CircularShiftLeft(AnArray,speDecalage.Value);
  PrintArray(AnArray, Memo2);
end;
 
procedure TForm1.Button2Click(Sender : TObject);
begin
  Memo2.Lines.add('================');
  CircularShiftRight(AnArray,speDecalage.Value);
  PrintArray(AnArray, Memo2);
end;
 
procedure TForm1.ResetClick(Sender : TObject);
begin
  ResetTab;
end;
 
procedure TForm1.CircularShiftRight(var mat : TMyArray; k : Byte);
Var
  Row, Col, M, N, I, J : Integer;
  Prev, Curr : Integer;
begin
  For j := 0 to k - 1 do
  begin
    Row := 0;
    Col := 0;
    M := cTabSize;
    N := cTabSize;
    While (Row < M) and (Col < N) do
    begin
      if ( ((row + 1) = m) or ((col + 1) = n)) then break;
 
      Prev := mat[(Row + 1) * cTabSize + Col];
      // On déplace la 1ere ligne vers la gauche
      For i := Col to (N-1) do
      begin
        Curr := mat[(Row * cTabSize) + i];
        mat[(Row * cTabSize) + i] := Prev;
        Prev := Curr;
      end;
 
      Inc(Row);
      // On déplace la derniere colonne vers le bas
      For I := Row to (M-1) do
      begin
        Curr := mat[(I * cTabSize) + (N-1)];
        mat[(I * cTabSize) + (N-1)] := Prev;
        Prev := Curr;
      end;
 
      Dec(N);
      // On déplace la derniere ligne vers la droite
      if (Col < N) then
      begin
        For i := (N-1) downto Col do
        begin
          Curr := mat[((M-1) * cTabSize) + I];
          mat[((M-1) * cTabSize) + i] := Prev;
          Prev := Curr;
        end;
      end;
 
      Dec(M);
      // On déplace la 1ere colonne vers le haut
      if (Row < M) then
      begin
        For i := (M-1) downto Row do
        begin
          Curr := mat[(I * cTabSize) + Col];
          mat[(I * cTabSize) + Col] := Prev;
          Prev := Curr;
        end;
      end;
      Inc(Col);
    end;
  end;
end;
 
procedure TForm1.CircularShiftLeft(var mat : TMyArray; k : Byte);
Var
  Row, Col, M, N, I, J : Integer;
  Prev, Curr : Integer;
begin
  For J := 0 to k-1 do
  begin
    Row := 0;
    Col := 0;
    M := cTabSize;
    N := cTabSize;
    While (Row < M) and (Col < N) do
    begin
      if ( ((row + 1) = m) or ((col + 1) = n)) then break;
 
      Prev := mat[(Row + 1) * cTabSize + (N-1)];
      // On déplace la 1ere ligne vers la droite
      For i := (N-1) DownTo Col do
      begin
        Curr := mat[(Row * cTabSize) + i];
        mat[(Row * cTabSize) + i] := Prev;
        Prev := Curr;
      end;
 
      Inc(Row);
      // On déplace la premiere colonne vers le bas
      For I := Row to (M-1) do
      begin
        Curr := mat[(I * cTabSize) + Col];
        mat[(I * cTabSize) + Col] := Prev;
        Prev := Curr;
      end;
      Inc(Col);
 
      // On déplace la derniere ligne vers la gauche
      if (Col < N) then
      begin
        For i := Col to (N-1) do
        begin
          Curr := mat[((M-1) * cTabSize) + I];
          mat[((M-1) * cTabSize) + i] := Prev;
          Prev := Curr;
        end;
      end;
      Dec(M);
      // On déplace la derniere colonne vers le haut
      if (Row < M) then
      begin
        For i := (M-1) downto Row do
        begin
          Curr := mat[(I * cTabSize) + (N-1)];
          mat[(I * cTabSize) + (N-1)] := Prev;
          Prev := Curr;
        end;
      end;
      Dec(N);
    end;
  end;
end;
 
procedure TForm1.PrintArray(arr : TMyArray; aMemo : TMemo);
var
  i, j, m : Integer;
  s, n : string;
begin
  //aMemo.Clear;
  m := cTabSize - 1;
  for i := 0 to m do
  begin
    s := '[';
    for j := 0 to m do
    begin
      n := Inttostr(Arr[i * cTabSize + j]);
      if length(n)<2 then n:= '0'+n;
      s := s + n;
      if j<(cTabSize-1) then s := s + ', ';
    end;
    s := s + ']';
    aMemo.Lines.Add(s);
  end;
  aMemo.Lines.Add('-----------------------');
end;
 
procedure TForm1.ResetTab;
Var
  i : Integer;
begin
  For i := 0 to (cTabSize * cTabSize) - 1 do
  begin
    AnArray[i] := i+1;
  end;
end;
 
end.

Merci

A+

**tourlourou** · 23/03/2020, 12h21

Bonjour,

Pour la matrice 3x3, le code que tu as donné ne conserve pas la bonne valeur au centre, mais recopie celle du milieu de la ligne du bas ???

Mes tests avec une matrice des nouveaux indices vont 2 fois plus vite (Delphi 5).

**BeanzMaster** · 23/03/2020, 15h51

Bonjour

Envoyé par tourlourou

Bonjour,

Pour la matrice 3x3, le code que tu as donné ne conserve pas la bonne valeur au centre, mais recopie celle du milieu de la ligne du bas ???

Bizarre ça car chez moi c'est tout bon. Je joins le code de mon application test. Pour vérifier CircularArrayShift.zip

A gauche la matrice source, à droite la matrice décalée à gauche de 1 et à droite de 1. Tout me semble correcte

Nom : 2020-03-23_154522.png
Affichages : 255
Taille : 2,1 Ko