Comment faire pivoter un tableau à deux dimensions ?

Question

Inspiré par Le message de Raymond Chen Par exemple, si vous avez un tableau 4x4 à deux dimensions, écrivez une fonction qui le fait pivoter de 90 degrés. Raymond propose une solution en pseudo-code, mais j'aimerais voir des exemples concrets.

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

Devient :

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

Mise à jour : La réponse de Nick est la plus simple, mais y a-t-il un moyen de faire mieux que n^2 ? Et si la matrice était de 10000x10000 ?

Answer 1

Algorithme en temps O(n^2) et en espace O(1) ( sans aucune solution de contournement et sans aucun artifice !)

Rotation de +90 :

1. Transposition
2. Inverser chaque ligne

Rotation de -90 :

1. Transposition
2. Inverser chaque colonne

Rotation de +180 :

Méthode 1 : Rotation de +90 deux fois

Méthode 2 : Inverser chaque ligne, puis chaque colonne

Rotation de -180 :

Méthode 1 : Rotation de -90 deux fois

Méthode 2 : Inverser chaque colonne, puis chaque ligne

Méthode 3 : Inverser par +180 car ils sont identiques

Answer 2

Le voici en C#

int[,] array = new int[4,4] {
    { 1,2,3,4 },
    { 5,6,7,8 },
    { 9,0,1,2 },
    { 3,4,5,6 }
};

int[,] rotated = RotateMatrix(array, 4);

static int[,] RotateMatrix(int[,] matrix, int n) {
    int[,] ret = new int[n, n];

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            ret[i, j] = matrix[n - j - 1, i];
        }
    }

    return ret;
}

Answer 3

Python :

rotated = zip(*original[::-1])

Pas cher, je sais.

Et dans le sens inverse des aiguilles d'une montre :

rotated_ccw = zip(*original)[::-1]

Answer 4

En voici une qui effectue la rotation sur place au lieu d'utiliser un tableau entièrement nouveau pour contenir le résultat. J'ai laissé de côté l'initialisation du tableau et son impression. Cela ne fonctionne que pour les tableaux carrés mais ils peuvent être de n'importe quelle taille. Le coût de la mémoire est égal à la taille d'un élément du tableau, donc vous pouvez effectuer la rotation d'un tableau aussi grand que vous le souhaitez. (le code est en C++)

int a[4][4];
int n=4;
int tmp;
for (int i=0; i<n/2; i++){
        for (int j=i; j<n-i-1; j++){
                tmp=a[i][j];
                a[i][j]=a[j][n-i-1];
                a[j][n-i-1]=a[n-i-1][n-j-1];
                a[n-i-1][n-j-1]=a[n-j-1][i];
                a[n-j-1][i]=tmp;
        }
}

Answer 5

Comme je l'ai dit dans mon message précédent, voici du code en C# qui implémente une rotation de matrice O(1) pour une matrice de n'importe quelle taille. Pour des raisons de brièveté et de lisibilité, il n'y a pas de contrôle d'erreur ni de contrôle de plage. Le code :

static void Main (string [] args)
{
  int [,]
    //  create an arbitrary matrix
    m = {{0, 1}, {2, 3}, {4, 5}};

  Matrix
    //  create wrappers for the data
    m1 = new Matrix (m),
    m2 = new Matrix (m),
    m3 = new Matrix (m);

  //  rotate the matricies in various ways - all are O(1)
  m1.RotateClockwise90 ();
  m2.Rotate180 ();
  m3.RotateAnitclockwise90 ();

  //  output the result of transforms
  System.Diagnostics.Trace.WriteLine (m1.ToString ());
  System.Diagnostics.Trace.WriteLine (m2.ToString ());
  System.Diagnostics.Trace.WriteLine (m3.ToString ());
}

class Matrix
{
  enum Rotation
  {
    None,
    Clockwise90,
    Clockwise180,
    Clockwise270
  }

  public Matrix (int [,] matrix)
  {
    m_matrix = matrix;
    m_rotation = Rotation.None;
  }

  //  the transformation routines
  public void RotateClockwise90 ()
  {
    m_rotation = (Rotation) (((int) m_rotation + 1) & 3);
  }

  public void Rotate180 ()
  {
    m_rotation = (Rotation) (((int) m_rotation + 2) & 3);
  }

  public void RotateAnitclockwise90 ()
  {
    m_rotation = (Rotation) (((int) m_rotation + 3) & 3);
  }

  //  accessor property to make class look like a two dimensional array
  public int this [int row, int column]
  {
    get
    {
      int
        value = 0;

      switch (m_rotation)
      {
      case Rotation.None:
        value = m_matrix [row, column];
        break;

      case Rotation.Clockwise90:
        value = m_matrix [m_matrix.GetUpperBound (0) - column, row];
        break;

      case Rotation.Clockwise180:
        value = m_matrix [m_matrix.GetUpperBound (0) - row, m_matrix.GetUpperBound (1) - column];
        break;

      case Rotation.Clockwise270:
        value = m_matrix [column, m_matrix.GetUpperBound (1) - row];
        break;
      }

      return value;
    }

    set
    {
      switch (m_rotation)
      {
      case Rotation.None:
        m_matrix [row, column] = value;
        break;

      case Rotation.Clockwise90:
        m_matrix [m_matrix.GetUpperBound (0) - column, row] = value;
        break;

      case Rotation.Clockwise180:
        m_matrix [m_matrix.GetUpperBound (0) - row, m_matrix.GetUpperBound (1) - column] = value;
        break;

      case Rotation.Clockwise270:
        m_matrix [column, m_matrix.GetUpperBound (1) - row] = value;
        break;
      }
    }
  }

  //  creates a string with the matrix values
  public override string ToString ()
  {
    int
      num_rows = 0,
      num_columns = 0;

    switch (m_rotation)
    {
    case Rotation.None:
    case Rotation.Clockwise180:
      num_rows = m_matrix.GetUpperBound (0);
      num_columns = m_matrix.GetUpperBound (1);
      break;

    case Rotation.Clockwise90:
    case Rotation.Clockwise270:
      num_rows = m_matrix.GetUpperBound (1);
      num_columns = m_matrix.GetUpperBound (0);
      break;
    }

    StringBuilder
      output = new StringBuilder ();

    output.Append ("{");

    for (int row = 0 ; row <= num_rows ; ++row)
    {
      if (row != 0)
      {
        output.Append (", ");
      }

      output.Append ("{");

      for (int column = 0 ; column <= num_columns ; ++column)
      {
        if (column != 0)
        {
          output.Append (", ");
        }

        output.Append (this [row, column].ToString ());
      }

      output.Append ("}");
    }

    output.Append ("}");

    return output.ToString ();
  }

  int [,]
    //  the original matrix
    m_matrix;

  Rotation
    //  the current view of the matrix
    m_rotation;
}

D'accord, je vais lever la main, il n'apporte en fait aucune modification au tableau d'origine lors de la rotation. Mais, dans un système OO, cela n'a pas d'importance tant que l'objet semble avoir été tourné pour les clients de la classe. Pour l'instant, la classe Matrix utilise des références aux données du tableau d'origine, donc changer une valeur de m1 changera aussi m2 et m3. Une petite modification du constructeur pour créer un nouveau tableau et y copier les valeurs permettra de résoudre ce problème.