Wie kann man ein zweidimensionales Feld drehen?

Question

Inspiriert durch Beitrag von Raymond Chen Wenn Sie ein zweidimensionales 4x4-Array haben, schreiben Sie eine Funktion, die es um 90 Grad dreht. Raymond verlinkt auf eine Lösung in Pseudocode, aber ich würde gerne etwas aus der Praxis sehen.

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

Wird:

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

Update : Die Antwort von Nick ist die einfachste, aber gibt es eine Möglichkeit, es besser zu machen als n^2? Was wäre, wenn die Matrix 10000x10000 wäre?

Answer 1

Es gibt tonnenweise guten Code hier, aber ich möchte nur zeigen, was geometrisch vor sich geht, damit Sie die Logik des Codes ein wenig besser verstehen können. Hier ist, wie ich dies angehen würde.

Verwechseln Sie dies zunächst nicht mit der Transposition, die sehr einfach ist.

Die Grundidee besteht darin, sie als Schichten zu behandeln und eine Schicht nach der anderen zu drehen.

sagen wir, wir haben einen 4x4

1   2   3   4
5   6   7   8
9   10  11  12
13  14  15  16

nach einer Drehung im Uhrzeigersinn um 90 ergibt sich

13  9   5   1
14  10  6   2   
15  11  7   3
16  12  8   4

Also zerlegen wir das Ganze, indem wir zunächst die 4 Ecken im Wesentlichen drehen

1           4

13          16

dann drehen wir den folgenden Diamanten, der ein wenig schief ist

    2
            8
9       
        15

und dann die 2. schräge Raute

        3
5           
            12
    14

Damit ist der äußere Rand abgedeckt. Wir machen also im Wesentlichen eine Schale nach der anderen, bis

schließlich das mittlere Feld (oder, wenn es ungerade ist, nur das letzte Element, das sich nicht bewegt)

6   7
10  11

Lassen Sie uns nun die Indizes der einzelnen Schichten herausfinden. Gehen wir davon aus, dass wir immer mit der äußersten Schicht arbeiten, so machen wir

[0,0] -> [0,n-1], [0,n-1] -> [n-1,n-1], [n-1,n-1] -> [n-1,0], and [n-1,0] -> [0,0]
[0,1] -> [1,n-1], [1,n-2] -> [n-1,n-2], [n-1,n-2] -> [n-2,0], and [n-2,0] -> [0,1]
[0,2] -> [2,n-2], [2,n-2] -> [n-1,n-3], [n-1,n-3] -> [n-3,0], and [n-3,0] -> [0,2]

und so weiter und so fort bis wir die Hälfte der Kante hinter uns haben

Das Muster ist also im Allgemeinen

[0,i] -> [i,n-i], [i,n-i] -> [n-1,n-(i+1)], [n-1,n-(i+1)] -> [n-(i+1),0], and [n-(i+1),0] to [0,i]

Answer 2

Wie ich bereits in meinem vorherigen Beitrag erwähnt habe, finden Sie hier einen Code in C#, der eine O(1)-Matrixrotation für eine beliebig große Matrix implementiert. Der Kürze und Lesbarkeit halber gibt es keine Fehler- oder Bereichsprüfung. Der 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;
}

OK, ich werde meine Hand heben, es macht eigentlich keine Änderungen am ursprünglichen Array beim Drehen. Aber in einem OO-System spielt das keine Rolle, solange das Objekt für die Clients der Klasse so aussieht, als ob es gedreht worden wäre. Im Moment verwendet die Klasse Matrix Referenzen auf die ursprünglichen Array-Daten, so dass jede Änderung des Wertes von m1 auch m2 und m3 ändert. Eine kleine Änderung im Konstruktor, um ein neues Array zu erstellen und die Werte dorthin zu kopieren, wird das Problem beheben.

Answer 3

Während eine Rotation der Daten an Ort und Stelle notwendig sein könnte (vielleicht um die physisch gespeicherte Darstellung zu aktualisieren), ist es einfacher und möglicherweise leistungsfähiger, eine indirekte Ebene zum Array-Zugriff hinzuzufügen, vielleicht eine Schnittstelle:

interface IReadableMatrix
{
    int GetValue(int x, int y);
}

Wenn Ihr Matrix diese Schnittstelle bereits implementiert, dann kann sie über eine Tapezierer Klasse wie diese:

class RotatedMatrix : IReadableMatrix
{
    private readonly IReadableMatrix _baseMatrix;

    public RotatedMatrix(IReadableMatrix baseMatrix)
    {
        _baseMatrix = baseMatrix;
    }

    int GetValue(int x, int y)
    {
        // transpose x and y dimensions
        return _baseMatrix(y, x);
    }
}

Auch das Drehen um +90/-90/180 Grad, das horizontale/vertikale Spiegeln und die Skalierung können auf diese Weise erreicht werden.

Die Leistung müsste in Ihrem spezifischen Szenario gemessen werden. Allerdings wurde die O(n^2)-Operation jetzt durch einen O(1)-Aufruf ersetzt. Es handelt sich um einen virtuellen Methodenaufruf, der es langsamer als der direkte Array-Zugriff, es hängt also davon ab, wie häufig das gedrehte Array nach der Drehung verwendet wird. Wenn es nur einmal verwendet wird, würde dieser Ansatz definitiv gewinnen. Wenn es gedreht und dann tagelang in einem lang laufenden System verwendet wird, könnte die In-Place-Rotation besser funktionieren. Es hängt auch davon ab, ob Sie die Vorlaufkosten in Kauf nehmen können.

Wie bei allen Leistungsfragen gilt: messen, messen, messen!

Answer 4

Dies ist eine bessere Version davon in Java: Ich habe es für eine Matrix mit einer anderen Breite und Höhe gemacht

• h ist hier die Höhe der Matrix nach dem Drehen

• w ist hier die Breite der Matrix nach dem Drehen

  public int[][] rotateMatrixRight(int[][] matrix) { / W and H are already swapped / int w = matrix.length; int h = matrix[0].length; int[][] ret = new int[h][w]; for (int i = 0; i < h; ++i) { for (int j = 0; j < w; ++j) { ret[i][j] = matrix[w - j - 1][i]; } } return ret; }

  public int[][] rotateMatrixLeft(int[][] matrix) { / W and H are already swapped / int w = matrix.length; int h = matrix[0].length;
  int[][] ret = new int[h][w]; for (int i = 0; i < h; ++i) { for (int j = 0; j < w; ++j) { ret[i][j] = matrix[j][h - i - 1]; } } return ret; }

Dieser Code basiert auf Nick Berardis Beitrag.

Answer 5

Ruby-way: .transpose.map &:reverse