Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Langage Pascal Discussion :

Rotation "circulaire" d'un tableau 2D


Sujet :

Langage Pascal

  1. #1
    Membre expert
    Rotation "circulaire" d'un tableau 2D
    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
    • "L'Homme devrait mettre autant d'ardeur à simplifier sa vie qu'il met à la compliquer" - Henri Bergson
    • "Bien des livres auraient été plus clairs s'ils n'avaient pas voulu être si clairs" - Emmanuel Kant
    • "La simplicité est la sophistication suprême" - Léonard De Vinci
    • "Ce qui est facile à comprendre ou à faire pour toi, ne l'est pas forcément pour l'autre." - Mon pèrei

    Mes projets sur Github - Blog - Site DVP

  2. #2
    Modérateur

    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 ?
    Delphi 5 Pro - Delphi 10.3.2 Rio Community Edition - CodeTyphon 6.90 sous Windows 10 ; CT 6.40 sous Ubuntu 18.04 (VM)
    . Ignorer la FAQ Delphi et les Cours et Tutoriels Delphi nuit gravement à notre code !

  3. #3
    Membre expert
    Bonjour

    Citation Envoyé par tourlourou Voir le message
    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.

    Citation Envoyé par tourlourou Voir le message

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

    [ 1,2,3, 4,5,6 7,8,9 ]
    Citation Envoyé par tourlourou Voir le message

    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.

    Citation Envoyé par tourlourou Voir le message

    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]
    • "L'Homme devrait mettre autant d'ardeur à simplifier sa vie qu'il met à la compliquer" - Henri Bergson
    • "Bien des livres auraient été plus clairs s'ils n'avaient pas voulu être si clairs" - Emmanuel Kant
    • "La simplicité est la sophistication suprême" - Léonard De Vinci
    • "Ce qui est facile à comprendre ou à faire pour toi, ne l'est pas forcément pour l'autre." - Mon pèrei

    Mes projets sur Github - Blog - Site DVP

  4. #4
    Membre expert
    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
    • "L'Homme devrait mettre autant d'ardeur à simplifier sa vie qu'il met à la compliquer" - Henri Bergson
    • "Bien des livres auraient été plus clairs s'ils n'avaient pas voulu être si clairs" - Emmanuel Kant
    • "La simplicité est la sophistication suprême" - Léonard De Vinci
    • "Ce qui est facile à comprendre ou à faire pour toi, ne l'est pas forcément pour l'autre." - Mon pèrei

    Mes projets sur Github - Blog - Site DVP

  5. #5
    Membre expert
    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
    • "L'Homme devrait mettre autant d'ardeur à simplifier sa vie qu'il met à la compliquer" - Henri Bergson
    • "Bien des livres auraient été plus clairs s'ils n'avaient pas voulu être si clairs" - Emmanuel Kant
    • "La simplicité est la sophistication suprême" - Léonard De Vinci
    • "Ce qui est facile à comprendre ou à faire pour toi, ne l'est pas forcément pour l'autre." - Mon pèrei

    Mes projets sur Github - Blog - Site DVP

  6. #6
    Rédacteur/Modérateur

    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.

  7. #7
    Membre expert
    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+
    • "L'Homme devrait mettre autant d'ardeur à simplifier sa vie qu'il met à la compliquer" - Henri Bergson
    • "Bien des livres auraient été plus clairs s'ils n'avaient pas voulu être si clairs" - Emmanuel Kant
    • "La simplicité est la sophistication suprême" - Léonard De Vinci
    • "Ce qui est facile à comprendre ou à faire pour toi, ne l'est pas forcément pour l'autre." - Mon pèrei

    Mes projets sur Github - Blog - Site DVP

  8. #8
    Modérateur

    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).
    Delphi 5 Pro - Delphi 10.3.2 Rio Community Edition - CodeTyphon 6.90 sous Windows 10 ; CT 6.40 sous Ubuntu 18.04 (VM)
    . Ignorer la FAQ Delphi et les Cours et Tutoriels Delphi nuit gravement à notre code !

  9. #9
    Membre expert
    Bonjour
    Citation Envoyé par tourlourou Voir le message
    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

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



    Citation Envoyé par tourlourou Voir le message

    Mes tests avec une matrice des nouveaux indices vont 2 fois plus vite (Delphi 5).
    Oui c'est clair qu'avec un tableau d'indices c'est surement plus rapide

    Merci

    Jérôme
    • "L'Homme devrait mettre autant d'ardeur à simplifier sa vie qu'il met à la compliquer" - Henri Bergson
    • "Bien des livres auraient été plus clairs s'ils n'avaient pas voulu être si clairs" - Emmanuel Kant
    • "La simplicité est la sophistication suprême" - Léonard De Vinci
    • "Ce qui est facile à comprendre ou à faire pour toi, ne l'est pas forcément pour l'autre." - Mon pèrei

    Mes projets sur Github - Blog - Site DVP