Discussion :

[BeanzMaster]

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]

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]

Bonjour

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.

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

LignexColonne

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

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.

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]

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]

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]

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.