Как Вы поворачиваете двумерную матрицу?

Вот моя версия Ruby (обратите внимание, что значения не отображены то же, но это все еще вращается, как описано).

def rotate(matrix)
  result = []
  4.times { |x|
    result[x] = []
    4.times { |y|
      result[x][y] = matrix[y][3 - x]
    }
  }

  result
end

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

def print_matrix(matrix)
  4.times { |y|
    4.times { |x|
      print "#{matrix[x][y]} "
    }
    puts ""
  }
end

print_matrix(matrix)
puts ""
print_matrix(rotate(matrix))

вывод:

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

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

Python:

rotated = zip(*original[::-1])  # On Python 3, list(zip(*original[::-1]))

Дешевый, я знаю.

И против часовой стрелки:

rotated_ccw = zip(*original)[::-1]  # On Python 3, list(zip(*original))[::-1]

, Как это работает: (Требуемый в комментариях)

zip(*original) подкачает оси 2-х массивов путем укладки соответствующих объектов из списков в новые списки. (* оператор говорит функции распределять содержавшие списки в аргументы)

>>> zip(*[[1,2,3],[4,5,6],[7,8,9]])
[[1,4,7],[2,5,8],[3,6,9]]

[::-1], оператор инвертирует элементы массива (см. Расширенные Части ).

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

Наконец, комбинируя эти два приведет к преобразованию вращения.

изменение в размещении [::-1] инвертирует списки в разных уровнях матрицы.

Вот тот, который делает вращение на месте вместо того, чтобы использовать абсолютно новый массив для содержания результата. Я бросил инициализацию массива и распечатывание его. Это только работает на квадратные антенные решетки, но они могут иметь любой размер. Память наверху равна размеру одного элемента массива, таким образом, можно сделать вращение столь большого массива, как Вы хотите.

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;
    }
}

Как я сказал в своем предыдущем сообщении, вот некоторый код в C#, который реализует O (1) матричное вращение для любой матрицы размера. Для краткости и удобочитаемости там не проверка ошибок или проверка диапазона. Код:

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;
}

хорошо, я подниму руку, она на самом деле не делает никаких модификаций к исходному массиву при вращении. Но, в системе OO, которая не имеет значения, пока объект похож, он был повернут клиентам класса. В данный момент Матричные ссылки использования класса на данные исходного массива, настолько изменяющиеся любое значение m1, также изменят m2 и m3. Небольшое изменение конструктора, чтобы создать новый массив и скопировать значения в него уладит это.

Пока вращение данных на месте могло бы быть необходимым (возможно, для обновления физически сохраненного представления), это становится более простым и возможно более производительным для добавления слоя косвенности на доступ к массиву, возможно, интерфейс:

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

, Если Ваш Matrix уже реализации этот интерфейс, то это может быть повернуто через декоратор класс как это:

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);
    }
}

Вращение +90/-90/180 градусы, зеркальное отражение горизонтально/вертикально и масштабирование может все быть достигнуто этим способом также.

Уровень должен был бы быть измерен в Вашем определенном сценарии. Однако O (n^2) операция был теперь заменен O (1) вызов. Это - виртуальный вызов метода, который является медленнее, чем прямой доступ к массиву, таким образом, это зависит от того, как часто повернутый массив используется после вращения. Если бы это используется однажды, то этот подход определенно победил бы. Если это повернуто тогда используемое в продолжительной системе в течение многих дней, то оперативное вращение могло бы работать лучше. Это также зависит, можно ли принять оплачиваемую авансом стоимость.

Как со всеми проблемами производительности, мерой, мерой, мерой!

Несколько человек уже подняли примеры, которые включают создание нового массива.

Несколько других вещей рассмотреть:

(a) Вместо того, чтобы на самом деле переместить данные, просто пересеките "повернутый" массив по-другому.

(b), Делающий оперативное вращение, может быть немного более хитрым. Вам будет нужно немного места царапины (вероятно, примерно равный одной строке или столбцу в размере). Существует древняя статья ACM о выполнении оперативного, транспонирует ( http://doi.acm.org/10.1145/355719.355729 ), но их примером кода является противный goto-загруженный ФОРТРАН.

Приложение:

http://doi.acm.org/10.1145/355611.355612 , другой, предположительно, выше, оперативный транспонирует алгоритм.

Nick's ответ работал бы на массив NxM также только с маленькой модификацией (в противоположность NxN).

string[,] orig = new string[n, m];
string[,] rot = new string[m, n];

...

for ( int i=0; i < n; i++ )
  for ( int j=0; j < m; j++ )
    rot[j, n - i - 1] = orig[i, j];

Один способ думать об этом состоит в том, что Вы переместили центр оси (0,0) от верхнего левого угла до правого верхнего угла. Вы просто транспонируете от одного до другого.

@dagorym: Ай, человек. Я зависал на это как польза, "я скучаю, что я могу обдумать" загадку. Я придумал свой оперативный код перемещения, но добрался здесь для нахождения Вашего в значительной степени идентичным моему... ах, хорошо. Здесь это находится в Ruby.

require 'pp'
n = 10
a = []
n.times { a << (1..n).to_a }

pp a

0.upto(n/2-1) do |i|
  i.upto(n-i-2) do |j|
    tmp             = a[i][j]
    a[i][j]         = a[n-j-1][i]
    a[n-j-1][i]     = a[n-i-1][n-j-1]
    a[n-i-1][n-j-1] = a[j][n-i-1]
    a[j][n-i-1]     = tmp
  end
end

pp a

short normal[4][4] = {{8,4,7,5},{3,4,5,7},{9,5,5,6},{3,3,3,3}};

short rotated[4][4];

for (int r = 0; r < 4; ++r)
{
  for (int c = 0; c < 4; ++c)
  {
    rotated[r][c] = normal[c][3-r];
  }
}

Простой метод C ++, хотя в большом массиве будут большие накладные расходы на память.

Если вы верите в Закон Деметры,

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);
    }
}
?>

Ruby-way: .transpose.map &:reverse

#include <iostream>
#include <iomanip>

using namespace std;
const int SIZE=3;
void print(int a[][SIZE],int);
void rotate(int a[][SIZE],int);

void main()
{
    int a[SIZE][SIZE]={{11,22,33},{44,55,66},{77,88,99}};
    cout<<"the array befor rotate\n";

    print(a,SIZE);
    rotate( a,SIZE);
    cout<<"the array after rotate\n";
    print(a,SIZE);
    cout<<endl;

}

void print(int a[][SIZE],int SIZE)
{
    int i,j;
    for(i=0;i<SIZE;i++)
       for(j=0;j<SIZE;j++)
          cout<<a[i][j]<<setw(4);
}

void rotate(int a[][SIZE],int SIZE)
{
    int temp[3][3],i,j;
    for(i=0;i<SIZE;i++)
       for(j=0;j<SIZE/2.5;j++)
       {
           temp[i][j]= a[i][j];
           a[i][j]= a[j][SIZE-i-1] ;
           a[j][SIZE-i-1] =temp[i][j];

       }
}

Все текущие решения имеют накладные расходы O (n ^ 2) в качестве рабочего места (это исключает этих грязных читеров ООП!). Вот решение с использованием памяти O (1), поворот матрицы на 90 градусов вправо. Расширяемость винта, эта присоска работает быстро!

#include <algorithm>
#include <cstddef>

// Rotates an NxN matrix of type T 90 degrees to the right.
template <typename T, size_t N>
void rotate_matrix(T (&matrix)[N][N])
{
    for(size_t i = 0; i < N; ++i)
        for(size_t j = 0; j <= (N-i); ++j)
            std::swap(matrix[i][j], matrix[j][i]);
}

ОТКАЗ ОТ ОТВЕТСТВЕННОСТИ: Я на самом деле не тестировал это. Давай поиграем в жучок!