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

Dies ist meine Implementierung in C, O(1) Speicherkomplexität, Rotation an Ort und Stelle, 90 Grad im Uhrzeigersinn:

#include <stdio.h>

#define M_SIZE 5

static void initMatrix();
static void printMatrix();
static void rotateMatrix();

static int m[M_SIZE][M_SIZE];

int main(void){
    initMatrix();
    printMatrix();
    rotateMatrix();
    printMatrix();

    return 0;
}

static void initMatrix(){
    int i, j;

    for(i = 0; i < M_SIZE; i++){
        for(j = 0; j < M_SIZE; j++){
            m[i][j] = M_SIZE*i + j + 1;
        }
    }
}

static void printMatrix(){
    int i, j;

    printf("Matrix\n");
    for(i = 0; i < M_SIZE; i++){
        for(j = 0; j < M_SIZE; j++){
            printf("%02d ", m[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}

static void rotateMatrix(){
    int r, c;

    for(r = 0; r < M_SIZE/2; r++){
        for(c = r; c < M_SIZE - r - 1; c++){
            int tmp = m[r][c];

            m[r][c] = m[M_SIZE - c - 1][r];
            m[M_SIZE - c - 1][r] = m[M_SIZE - r - 1][M_SIZE - c - 1];
            m[M_SIZE - r - 1][M_SIZE - c - 1] = m[c][M_SIZE - r - 1];
            m[c][M_SIZE - r - 1] = tmp;
        }
    }
}

Answer 2

Große Antworten, aber für diejenigen, die für eine DRY JavaScript-Code für diese suchen - sowohl +90 Grad und -90 Grad:

          // Input: 1 2 3
          //        4 5 6
          //        7 8 9

          // Transpose: 
          //       1 4 7
          //       2 5 8
          //       3 6 9

          // Output: 
          // +90 Degree:
          //       7 4 1
          //       8 5 2
          //       9 6 3

          // -90 Degree:
          //      3 6 9
          //      2 5 8
          //      1 4 7

          // Rotate +90
         function rotate90(matrix) {

           matrix = transpose(matrix);
           matrix.map(function(array) {
             array.reverse();
           });

           return matrix;
         }

          // Rotate -90
         function counterRotate90(matrix) {
           var result = createEmptyMatrix(matrix.length);
           matrix = transpose(matrix);
           var counter = 0;

           for (var i = matrix.length - 1; i >= 0; i--) {
             result[counter] = matrix[i];
             counter++;
           }

           return result;
         }

          // Create empty matrix
         function createEmptyMatrix(len) {
           var result = new Array();
           for (var i = 0; i < len; i++) {
             result.push([]);
           }
           return result;
         }

          // Transpose the matrix
         function transpose(matrix) {
           // make empty array
           var len = matrix.length;
           var result = createEmptyMatrix(len);

           for (var i = 0; i < matrix.length; i++) {
             for (var j = 0; j < matrix[i].length; j++) {
               var temp = matrix[i][j];
               result[j][i] = temp;
             }
           }
           return result;
         }

          // Test Cases
         var array1 = [
           [1, 2],
           [3, 4]
         ];
         var array2 = [
           [1, 2, 3],
           [4, 5, 6],
           [7, 8, 9]
         ];
         var array3 = [
           [1, 2, 3, 4],
           [5, 6, 7, 8],
           [9, 10, 11, 12],
           [13, 14, 15, 16]
         ];

          // +90 degress Rotation Tests

         var test1 = rotate90(array1);
         var test2 = rotate90(array2);
         var test3 = rotate90(array3);
         console.log(test1);
         console.log(test2);
         console.log(test3);

          // -90 degress Rotation Tests
         var test1 = counterRotate90(array1);
         var test2 = counterRotate90(array2);
         var test3 = counterRotate90(array3);
         console.log(test1);
         console.log(test2);
         console.log(test3);

Answer 3

PHP:

<?php    
$a = array(array(1,2,3,4),array(5,6,7,8),array(9,0,1,2),array(3,4,5,6));
$b = array(); //result

while(count($a)>0)
{
    $b[count($a[0])-1][] = array_shift($a[0]);
    if (count($a[0])==0)
    {
         array_shift($a);
    }
}

Ab PHP5.6 kann die Array-Transposition mit einem Sleak durchgeführt werden array_map() anrufen. Mit anderen Worten: Spalten werden in Zeilen umgewandelt.

Code: ( Demo )

$array = [
    [1, 2, 3, 4],
    [5, 6, 7, 8],
    [9, 0, 1, 2],
    [3, 4, 5, 6]
];
$transposed = array_map(null, ...$array);

$transposed:

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

Answer 4

Betrachten Sie die Matrizen unter linearen Gesichtspunkten:

    1 2 3        0 0 1
A = 4 5 6    B = 0 1 0
    7 8 9        1 0 0

Nehmen Sie nun A transponieren

     1 4 7
A' = 2 5 8
     3 6 9

Und betrachten Sie die Wirkung von A' auf B bzw. B auf A'.
Respektive:

      7 4 1          3 6 9
A'B = 8 5 2    BA' = 2 5 8
      9 6 3          1 4 7

Dies ist für jede n x n-Matrix erweiterbar. Und die Anwendung dieses Konzepts schnell in Code:

void swapInSpace(int** mat, int r1, int c1, int r2, int c2)
{
    mat[r1][c1] ^= mat[r2][c2];
    mat[r2][c2] ^= mat[r1][c1];
    mat[r1][c1] ^= mat[r2][c2];
}

void transpose(int** mat, int size)
{
    for (int i = 0; i < size; i++)
    {
        for (int j = (i + 1); j < size; j++)
        {
            swapInSpace(mat, i, j, j, i);
        }
    }
}

void rotate(int** mat, int size)
{
    //Get transpose
    transpose(mat, size);

    //Swap columns
    for (int i = 0; i < size / 2; i++)
    {
        for (int j = 0; j < size; j++)
        {
            swapInSpace(mat, i, j, size - (i + 1), j);
        }
    }
}

Answer 5

C#-Code zum Drehen von [n,m] 2D-Arrays um 90 Grad nach rechts

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace MatrixProject
{
    // mattrix class

    class Matrix{
        private int rows;
        private int cols;
        private int[,] matrix;

        public Matrix(int n){
            this.rows = n;
            this.cols = n;
            this.matrix = new int[this.rows,this.cols];

        }

        public Matrix(int n,int m){
            this.rows = n;
            this.cols = m;

            this.matrix = new int[this.rows,this.cols];
        }

        public void Show()
        {
            for (var i = 0; i < this.rows; i++)
            {
                for (var j = 0; j < this.cols; j++) {
                    Console.Write("{0,3}", this.matrix[i, j]);
                }
                Console.WriteLine();
            }                
        }

        public void ReadElements()
        {
           for (var i = 0; i < this.rows; i++)
                for (var j = 0; j < this.cols; j++)
                {
                    Console.Write("element[{0},{1}]=",i,j);
                    this.matrix[i, j] = Convert.ToInt32(Console.ReadLine());
                }            
        }

        // rotate [n,m] 2D array by 90 deg right
        public void Rotate90DegRight()
        {

            // create a mirror of current matrix
            int[,] mirror = this.matrix;

            // create a new matrix
            this.matrix = new int[this.cols, this.rows];

            for (int i = 0; i < this.rows; i++)
            {
                for (int j = 0; j < this.cols; j++)
                {
                    this.matrix[j, this.rows - i - 1] = mirror[i, j];
                }
            }

            // replace cols count with rows count
            int tmp = this.rows;
            this.rows = this.cols;
            this.cols = tmp;           
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            Matrix myMatrix = new Matrix(3,4);
            Console.WriteLine("Enter matrix elements:");
            myMatrix.ReadElements();
            Console.WriteLine("Matrix elements are:");
            myMatrix.Show();
            myMatrix.Rotate90DegRight();
            Console.WriteLine("Matrix rotated at 90 deg are:");
            myMatrix.Show();
            Console.ReadLine();
        }
    }
}

Ergebnis:

    Enter matrix elements:
    element[0,0]=1
    element[0,1]=2
    element[0,2]=3
    element[0,3]=4
    element[1,0]=5
    element[1,1]=6
    element[1,2]=7
    element[1,3]=8
    element[2,0]=9
    element[2,1]=10
    element[2,2]=11
    element[2,3]=12
    Matrix elements are:
      1  2  3  4
      5  6  7  8
      9 10 11 12
    Matrix rotated at 90 deg are:
      9  5  1
     10  6  2
     11  7  3
     12  8  4