Bagaimana Anda memutar array dua dimensi?

Terinspirasi oleh posting Raymond Chen , katakan Anda memiliki array dua dimensi 4x4, tulis fungsi yang memutarnya 90 derajat. Link Raymond ke solusi dalam kode pseudo, tapi saya ingin melihat beberapa hal dunia nyata.

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

Menjadi:

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

Pembaruan : Jawaban Nick adalah yang paling mudah, tetapi apakah ada cara untuk melakukannya lebih baik daripada n ^ 2? Bagaimana jika matriksnya 10000x10000?

Ini dia dalam 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;
}

O (n ^ 2) waktu dan O (1) algoritma ruang (tanpa solusi dan hal-hal saputangan!)

Putar +90:

1. Mengubah urutan
2. Balikkan setiap baris

Putar oleh -90:

Metode 1:

1. Mengubah urutan
2. Balikkan setiap kolom

Metode 2:

1. Balikkan setiap baris
2. Mengubah urutan

Putar oleh +180:

Metode 1 : Putar oleh +90 dua kali

Metode 2 : Membalikkan setiap baris dan lalu membalikkan setiap kolom (Transpose)

Putar dengan -180:

Metode 1 : Putar oleh -90 dua kali

Metode 2 : Balikkan setiap kolom lalu balikkan setiap baris

Metode 3 : Putar oleh +180 karena sama

Saya ingin menambahkan sedikit lebih detail. Dalam jawaban ini, konsep-konsep kunci diulangi, langkahnya lambat dan sengaja berulang. Solusi yang diberikan di sini bukan yang paling kompak secara sintaksis, namun, ditujukan untuk mereka yang ingin mempelajari apa itu rotasi matriks dan implementasi yang dihasilkan.

Pertama, apa itu matriks? Untuk keperluan jawaban ini, sebuah matriks hanyalah sebuah kotak dengan lebar dan tinggi yang sama. Catatan, lebar dan tinggi matriks bisa berbeda, tetapi untuk kesederhanaan, tutorial ini hanya mempertimbangkan matriks dengan lebar dan tinggi yang sama ( matriks persegi ). Dan ya, matriks adalah bentuk jamak dari matriks.

Contoh matriks adalah: 2 × 2, 3 × 3 atau 5 × 5. Atau, lebih umum, N × N. Matriks 2 × 2 akan memiliki 4 kotak karena 2 × 2 = 4. Matriks 5 × 5 akan memiliki 25 kotak karena 5 × 5 = 25. Setiap kotak disebut elemen atau entri. Kami akan mewakili setiap elemen dengan tanda titik ( .) pada diagram di bawah ini:

Matriks 2 × 2

. .
. .

Matriks 3 × 3

. . .
. . .
. . .

4 × 4 matriks

. . . .
. . . .
. . . .
. . . .

Jadi, apa artinya memutar matriks? Mari kita mengambil matriks 2 × 2 dan meletakkan beberapa angka di setiap elemen sehingga rotasi dapat diamati:

0 1
2 3

Memutar ini 90 derajat memberi kita:

2 0
3 1

Kami benar-benar mengubah seluruh matriks satu kali ke kanan seperti memutar setir mobil. Mungkin membantu untuk memikirkan “membalik” matriks ke sisi kanannya. Kami ingin menulis sebuah fungsi, dengan Python, yang mengambil matriks dan berputar sekali ke kanan. Tanda tangan fungsi adalah:

def rotate(matrix):
    # Algorithm goes here.

Matriks akan didefinisikan menggunakan array dua dimensi:

matrix = [
    [0,1],
    [2,3]
]

Oleh karena itu posisi indeks pertama mengakses baris. Posisi indeks kedua mengakses kolom:

matrix[row][column]

Kami akan mendefinisikan fungsi utilitas untuk mencetak matriks.

def print_matrix(matrix):
    for row in matrix:
        print row

Salah satu metode memutar matriks adalah dengan melakukannya satu lapis pada satu waktu. Tapi apa itu layer? Pikirkan bawang. Sama seperti lapisan bawang, saat setiap lapisan dihilangkan, kami bergerak ke tengah. Analogi lainnya adalah boneka Matryoshka atau permainan pass-the-parcel.

Lebar dan tinggi matriks menentukan jumlah lapisan dalam matriks itu. Mari kita gunakan simbol yang berbeda untuk setiap layer:

Matriks 2 × 2 memiliki 1 lapisan

. .
. .

Matriks 3 × 3 memiliki 2 lapisan

. . .
. x .
. . .

Matriks 4 × 4 memiliki 2 lapisan

. . . .
. x x .
. x x .
. . . .

Matriks 5 × 5 memiliki 3 lapisan

. . . . .
. x x x .
. x O x .
. x x x .
. . . . .

Matriks 6 × 6 memiliki 3 lapisan

. . . . . .
. x x x x .
. x O O x .
. x O O x .
. x x x x .
. . . . . .

Matriks 7 × 7 memiliki 4 lapisan

. . . . . . .
. x x x x x .
. x O O O x .
. x O - O x .
. x O O O x .
. x x x x x .
. . . . . . .

Anda mungkin memperhatikan bahwa penambahan lebar dan tinggi matriks satu per satu, tidak selalu menambah jumlah lapisan. Mengambil matriks di atas dan mentabulasi lapisan dan dimensi, kita melihat jumlah lapisan meningkat satu kali untuk setiap dua penambahan lebar dan tinggi:

+-----+--------+
| N×N | Layers |
+-----+--------+
| 1×1 |      1 |
| 2×2 |      1 |
| 3×3 |      2 |
| 4×4 |      2 |
| 5×5 |      3 |
| 6×6 |      3 |
| 7×7 |      4 |
+-----+--------+

Namun, tidak semua lapisan perlu diputar. Matriks 1 × 1 adalah sama sebelum dan sesudah rotasi. Lapisan pusat 1 × 1 selalu sama sebelum dan sesudah rotasi tidak peduli seberapa besar keseluruhan matriks:

+-----+--------+------------------+
| N×N | Layers | Rotatable Layers |
+-----+--------+------------------+
| 1×1 |      1 |                0 |
| 2×2 |      1 |                1 |
| 3×3 |      2 |                1 |
| 4×4 |      2 |                2 |
| 5×5 |      3 |                2 |
| 6×6 |      3 |                3 |
| 7×7 |      4 |                3 |
+-----+--------+------------------+

Dengan matriks N × N, bagaimana kita dapat secara program menentukan jumlah lapisan yang perlu kita putar? Jika kita membagi lebar atau tinggi dengan dua dan mengabaikan sisanya kita mendapatkan hasil berikut.

+-----+--------+------------------+---------+
| N×N | Layers | Rotatable Layers |   N/2   |
+-----+--------+------------------+---------+
| 1×1 |      1 |                0 | 1/2 = 0 |
| 2×2 |      1 |                1 | 2/2 = 1 |
| 3×3 |      2 |                1 | 3/2 = 1 |
| 4×4 |      2 |                2 | 4/2 = 2 |
| 5×5 |      3 |                2 | 5/2 = 2 |
| 6×6 |      3 |                3 | 6/2 = 3 |
| 7×7 |      4 |                3 | 7/2 = 3 |
+-----+--------+------------------+---------+

Perhatikan seberapa N/2cocok dengan jumlah layer yang perlu diputar? Kadang-kadang jumlah lapisan yang dapat diputar adalah kurang dari jumlah total lapisan dalam matriks. Ini terjadi ketika lapisan terdalam hanya terbentuk dari satu elemen (yaitu matriks 1 × 1) dan karenanya tidak perlu diputar. Itu hanya diabaikan.

Kami pasti akan membutuhkan informasi ini dalam fungsi kami untuk memutar matriks, jadi mari kita tambahkan sekarang:

def rotate(matrix):
    size = len(matrix)
    # Rotatable layers only.
    layer_count = size / 2

Sekarang kita tahu apa itu lapisan dan bagaimana menentukan jumlah lapisan yang sebenarnya perlu dirotasi, bagaimana kita mengisolasi satu lapisan sehingga kita bisa memutarnya? Pertama, kami memeriksa matriks dari lapisan terluar, ke dalam, ke lapisan terdalam. Matriks 5 × 5 memiliki tiga lapisan total dan dua lapisan yang perlu dirotasi:

. . . . .
. x x x .
. x O x .
. x x x .
. . . . .

Mari kita lihat kolom terlebih dahulu. Posisi kolom menentukan lapisan terluar, dengan asumsi kita menghitung dari 0, adalah 0 dan 4:

+--------+-----------+
| Column | 0 1 2 3 4 |
+--------+-----------+
|        | . . . . . |
|        | . x x x . |
|        | . x O x . |
|        | . x x x . |
|        | . . . . . |
+--------+-----------+

0 dan 4 juga merupakan posisi baris untuk lapisan terluar.

+-----+-----------+
| Row |           |
+-----+-----------+
|   0 | . . . . . |
|   1 | . x x x . |
|   2 | . x O x . |
|   3 | . x x x . |
|   4 | . . . . . |
+-----+-----------+

Ini akan selalu terjadi karena lebar dan tinggi adalah sama. Oleh karena itu kita dapat mendefinisikan posisi kolom dan baris pada layer hanya dengan dua nilai (bukan empat).

Pindah ke dalam ke lapisan kedua, posisi kolom adalah 1 dan 3. Dan, ya, Anda dapat menebaknya, itu sama untuk baris. Penting untuk dipahami bahwa kami harus menambah dan mengurangi posisi baris dan kolom saat bergerak ke dalam ke lapisan berikutnya.

+-----------+---------+---------+---------+
|   Layer   |  Rows   | Columns | Rotate? |
+-----------+---------+---------+---------+
| Outermost | 0 and 4 | 0 and 4 | Yes     |
| Inner     | 1 and 3 | 1 and 3 | Yes     |
| Innermost | 2       | 2       | No      |
+-----------+---------+---------+---------+

Jadi, untuk memeriksa setiap lapisan, kami ingin loop dengan penghitung yang meningkat dan menurun yang mewakili gerakan ke dalam, mulai dari lapisan terluar. Kami akan menyebutnya 'loop layer' kami.

def rotate(matrix):
    size = len(matrix)
    layer_count = size / 2

    for layer in range(0, layer_count):
        first = layer
        last = size - first - 1
        print 'Layer %d: first: %d, last: %d' % (layer, first, last)

# 5x5 matrix
matrix = [
    [ 0, 1, 2, 3, 4],
    [ 5, 6, 6, 8, 9],
    [10,11,12,13,14],
    [15,16,17,18,19],
    [20,21,22,23,24]
]

rotate(matrix)

Kode di atas memotong melalui posisi (baris dan kolom) dari setiap lapisan yang perlu dirotasi.

Layer 0: first: 0, last: 4
Layer 1: first: 1, last: 3

Kami sekarang memiliki lingkaran yang menyediakan posisi baris dan kolom dari setiap lapisan. Variabel firstdan lastmengidentifikasi posisi indeks dari baris dan kolom pertama dan terakhir. Mengacu kembali ke tabel baris dan kolom kami:

+--------+-----------+
| Column | 0 1 2 3 4 |
+--------+-----------+
|        | . . . . . |
|        | . x x x . |
|        | . x O x . |
|        | . x x x . |
|        | . . . . . |
+--------+-----------+

+-----+-----------+
| Row |           |
+-----+-----------+
|   0 | . . . . . |
|   1 | . x x x . |
|   2 | . x O x . |
|   3 | . x x x . |
|   4 | . . . . . |
+-----+-----------+

Jadi kita dapat menavigasi melalui lapisan-lapisan matriks. Sekarang kita membutuhkan cara menavigasi di dalam lapisan sehingga kita dapat memindahkan elemen di sekitar lapisan itu. Catatan, elemen tidak pernah 'melompat' dari satu layer ke layer lain, tetapi mereka bergerak di dalam layer masing-masing.

Memutar setiap elemen dalam suatu lapisan akan memutar seluruh lapisan. Memutar semua lapisan dalam matriks akan memutar seluruh matriks. Kalimat ini sangat penting, jadi cobalah yang terbaik untuk memahaminya sebelum melanjutkan.

Sekarang, kita membutuhkan cara untuk benar-benar memindahkan elemen, yaitu memutar setiap elemen, dan selanjutnya layer, dan akhirnya matriks. Untuk mempermudah, kami akan kembali ke matriks 3x3 - yang memiliki satu lapisan yang dapat diputar.

0 1 2
3 4 5
6 7 8

Lingkaran lapisan kami menyediakan indeks kolom pertama dan terakhir, serta baris pertama dan terakhir:

+-----+-------+
| Col | 0 1 2 |
+-----+-------+
|     | 0 1 2 |
|     | 3 4 5 |
|     | 6 7 8 |
+-----+-------+

+-----+-------+
| Row |       |
+-----+-------+
|   0 | 0 1 2 |
|   1 | 3 4 5 |
|   2 | 6 7 8 |
+-----+-------+

Karena matriks kita selalu kuadrat, kita hanya perlu dua variabel, firstdan last, karena posisi indeks sama untuk baris dan kolom.

def rotate(matrix):
    size = len(matrix)
    layer_count = size / 2

    # Our layer loop i=0, i=1, i=2
    for layer in range(0, layer_count):

        first = layer
        last = size - first - 1

        # We want to move within a layer here.

Variabel pertama dan terakhir dapat dengan mudah digunakan untuk merujuk empat sudut matriks. Ini karena sudut-sudut itu sendiri dapat didefinisikan menggunakan berbagai permutasi dari firstdan last(tanpa pengurangan, penambahan atau offset variabel-variabel tersebut):

+---------------+-------------------+-------------+
| Corner        | Position          | 3x3 Values  |
+---------------+-------------------+-------------+
| top left      | (first, first)    | (0,0)       |
| top right     | (first, last)     | (0,2)       |
| bottom right  | (last, last)      | (2,2)       |
| bottom left   | (last, first)     | (2,0)       |
+---------------+-------------------+-------------+

Untuk alasan ini, kami memulai rotasi kami di empat sudut terluar - kami akan memutarnya terlebih dahulu. Mari kita sorot dengan mereka *.

* 1 *
3 4 5
* 7 *

Kami ingin bertukar masing *- masing dengan di *sebelah kanannya. Jadi mari kita lanjutkan mencetak sudut-sudut kita yang didefinisikan hanya menggunakan berbagai permutasi dari firstdan last:

def rotate(matrix):
    size = len(matrix)
    layer_count = size / 2
    for layer in range(0, layer_count):

        first = layer
        last = size - first - 1

        top_left = (first, first)
        top_right = (first, last)
        bottom_right = (last, last)
        bottom_left = (last, first)

        print 'top_left: %s' % (top_left)
        print 'top_right: %s' % (top_right)
        print 'bottom_right: %s' % (bottom_right)
        print 'bottom_left: %s' % (bottom_left)

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

rotate(matrix)

Output harus:

top_left: (0, 0)
top_right: (0, 2)
bottom_right: (2, 2)
bottom_left: (2, 0)

Sekarang kita bisa dengan mudah menukar masing-masing sudut dari dalam loop layer kita:

def rotate(matrix):
    size = len(matrix)
    layer_count = size / 2
    for layer in range(0, layer_count):

        first = layer
        last = size - first - 1

        top_left = matrix[first][first]
        top_right = matrix[first][last]
        bottom_right = matrix[last][last]
        bottom_left = matrix[last][first]

        # bottom_left -> top_left
        matrix[first][first] = bottom_left
        # top_left -> top_right
        matrix[first][last] = top_left
        # top_right -> bottom_right
        matrix[last][last] = top_right
        # bottom_right -> bottom_left
        matrix[last][first] = bottom_right


print_matrix(matrix)
print '---------'
rotate(matrix)
print_matrix(matrix)

Matriks sebelum memutar sudut:

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

Matriks setelah sudut berputar:

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

Bagus! Kami telah berhasil memutar setiap sudut matriks. Namun, kami belum memutar elemen di tengah setiap lapisan. Jelas kita membutuhkan cara iterasi di dalam layer.

Masalahnya adalah, satu-satunya loop dalam fungsi kita sejauh ini (loop layer kita), bergerak ke lapisan berikutnya pada setiap iterasi. Karena matriks kami hanya memiliki satu lapisan yang dapat diputar, loop lapisan keluar setelah hanya memutar sudut-sudutnya. Mari kita lihat apa yang terjadi dengan matriks 5x5 yang lebih besar (di mana dua lapisan perlu diputar). Kode fungsi telah dihilangkan, tetapi tetap sama seperti di atas:

matrix = [
[0, 1, 2, 3, 4],
[5, 6, 7, 8, 9],
[10, 11, 12, 13, 14],
[15, 16, 17, 18, 19],
[20, 21, 22, 23, 24]
]
print_matrix(matrix)
print '--------------------'
rotate(matrix)
print_matrix(matrix)

Outputnya adalah:

[20,  1,  2,  3,  0]
[ 5, 16,  7,  6,  9]
[10, 11, 12, 13, 14]
[15, 18, 17,  8, 19]
[24, 21, 22, 23,  4]

Seharusnya tidak mengherankan bahwa sudut-sudut lapisan terluar telah diputar, tetapi, Anda juga dapat melihat sudut-sudut lapisan berikutnya (ke dalam) juga telah diputar. Ini masuk akal. Kami telah menulis kode untuk menavigasi lapisan dan juga untuk memutar sudut setiap lapisan. Ini terasa seperti kemajuan, tetapi sayangnya kita harus mengambil langkah mundur. Tidak ada gunanya pindah ke lapisan berikutnya sampai lapisan (luar) sebelumnya telah diputar penuh. Yaitu, sampai setiap elemen dalam lapisan telah diputar. Hanya memutar sudut tidak akan berhasil!

Ambil napas dalam-dalam. Kami membutuhkan loop lain. Loop bersarang tidak kurang. Lingkaran bersarang yang baru, akan menggunakan variabel firstdan last, ditambah offset untuk menavigasi dalam lapisan. Kami akan menyebut loop baru ini sebagai 'loop elemen'. Lingkaran elemen akan mengunjungi setiap elemen di sepanjang baris atas, setiap elemen di sisi kanan, setiap elemen di sepanjang baris bawah dan setiap elemen di sisi kiri.

• Bergerak maju sepanjang baris atas membutuhkan indeks kolom yang akan bertambah.
• Pindah ke sisi kanan membutuhkan indeks baris yang akan bertambah.
• Bergerak mundur di sepanjang bagian bawah membutuhkan indeks kolom harus dikurangi.
• Pindah ke sisi kiri membutuhkan indeks baris harus dikurangi.

Ini kedengarannya rumit, tetapi itu dibuat mudah karena berapa kali kita menambah dan mengurangi untuk mencapai hal di atas tetap sama di sepanjang keempat sisi matriks. Sebagai contoh:

• Pindahkan 1 elemen di baris atas.
• Pindahkan 1 elemen ke sisi kanan.
• Pindahkan 1 elemen ke belakang di sepanjang baris bawah.
• Pindahkan 1 elemen ke sisi kiri.

Ini berarti kita dapat menggunakan variabel tunggal dalam kombinasi dengan firstdan lastvariabel untuk bergerak di dalam layer. Mungkin membantu untuk mencatat bahwa bergerak melintasi baris atas dan ke bawah di sisi kanan keduanya membutuhkan penambahan. Saat bergerak mundur di sepanjang bagian bawah dan di sisi kiri keduanya membutuhkan penurunan.

def rotate(matrix):
    size = len(matrix)
    layer_count = size / 2

    # Move through layers (i.e. layer loop).
    for layer in range(0, layer_count):

            first = layer
            last = size - first - 1

            # Move within a single layer (i.e. element loop).
            for element in range(first, last):

                offset = element - first

                # 'element' increments column (across right)
                top_element = (first, element)
                # 'element' increments row (move down)
                right_side = (element, last)
                # 'last-offset' decrements column (across left)
                bottom = (last, last-offset)
                # 'last-offset' decrements row (move up)
                left_side = (last-offset, first)

                print 'top: %s' % (top)
                print 'right_side: %s' % (right_side)
                print 'bottom: %s' % (bottom)
                print 'left_side: %s' % (left_side)

Sekarang kita hanya perlu menetapkan bagian atas ke sisi kanan, sisi kanan ke bawah, bawah ke sisi kiri, dan sisi kiri ke atas. Menyatukan semua ini kita dapatkan:

def rotate(matrix):
    size = len(matrix)
    layer_count = size / 2

    for layer in range(0, layer_count):
        first = layer
        last = size - first - 1

        for element in range(first, last):
            offset = element - first

            top = matrix[first][element]
            right_side = matrix[element][last]
            bottom = matrix[last][last-offset]
            left_side = matrix[last-offset][first]

            matrix[first][element] = left_side
            matrix[element][last] = top
            matrix[last][last-offset] = right_side
            matrix[last-offset][first] = bottom

Mengingat matriks:

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

rotateFungsi kami menghasilkan:

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

Python:

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

dan berlawanan arah jarum jam:

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

Bagaimana ini bekerja:

zip(*original)akan menukar sumbu array 2d dengan menumpuk item yang sesuai dari daftar ke daftar baru. ( *Operator memberi tahu fungsi untuk mendistribusikan daftar yang ada ke dalam argumen)

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

The [::-1]elemen membalikkan pernyataan array (lihat Diperpanjang Slices atau pertanyaan ini ):

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

Akhirnya, menggabungkan keduanya akan menghasilkan transformasi rotasi.

Perubahan penempatan [::-1]akan membalik daftar di berbagai tingkat matriks.

Berikut adalah salah satu yang melakukan rotasi di tempat daripada menggunakan array yang sama sekali baru untuk menahan hasilnya. Saya telah mengabaikan inisialisasi array dan mencetaknya. Ini hanya berfungsi untuk array persegi tetapi ukurannya bisa berapa saja. Memori overhead sama dengan ukuran satu elemen array sehingga Anda dapat melakukan rotasi array sebesar yang Anda inginkan.

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

Ada banyak kode bagus di sini tapi saya hanya ingin menunjukkan apa yang terjadi secara geometris sehingga Anda dapat memahami logika kode sedikit lebih baik. Inilah cara saya mendekati ini.

pertama-tama, jangan bingung dengan transposisi yang sangat mudah ..

ide basica adalah untuk memperlakukannya sebagai lapisan dan kami memutar satu lapisan pada satu waktu ..

misalkan kita punya 4x4

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

setelah kita putar searah jarum jam dengan 90 kita dapatkan

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

jadi mari kita uraikan ini, pertama kita memutar 4 sudut dasarnya

1           4


13          16

lalu kita putar berlian berikut yang agak miring

    2
            8
9       
        15

dan kemudian berlian miring ke-2

        3
5           
            12
    14

sehingga menjaga tepi luar jadi pada dasarnya kita melakukan itu satu per satu sampai

akhirnya alun-alun (atau jika itu aneh hanya elemen terakhir yang tidak bergerak)

6   7
10  11

jadi sekarang mari kita cari tahu indeks masing-masing lapisan, anggap kita selalu bekerja dengan lapisan terluar, kita lakukan

[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]

seterusnya dan seterusnya sampai kita berada di tengah jalan

jadi secara umum polanya

[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]

Seperti yang saya katakan di posting saya sebelumnya, inilah beberapa kode dalam C # yang mengimplementasikan rotasi matriks O (1) untuk matriks ukuran apa pun. Untuk singkatnya dan mudah dibaca tidak ada pengecekan error atau pengecekan jangkauan. Kode:

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, saya akan mengangkat tangan saya, itu tidak benar-benar melakukan modifikasi pada array asli ketika berputar. Tapi, dalam sistem OO yang tidak masalah selama objeknya terlihat diputar ke klien kelas. Saat ini, kelas Matrix menggunakan referensi ke data array asli sehingga mengubah nilai m1 juga akan mengubah m2 dan m3. Perubahan kecil ke konstruktor untuk membuat array baru dan menyalin nilai-nilai itu akan memilahnya.

Sementara memutar data di tempat mungkin diperlukan (mungkin untuk memperbarui representasi yang tersimpan secara fisik), menjadi lebih sederhana dan mungkin lebih banyak pemain untuk menambahkan lapisan tipuan ke akses array, mungkin sebuah antarmuka:

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

Jika Anda Matrixsudah mengimplementasikan antarmuka ini, maka itu dapat diputar melalui kelas dekorator seperti ini:

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

Memutar + 90 / -90 / 180 derajat, membalik secara horizontal / vertikal dan penskalaan semua dapat dicapai dengan cara ini juga.

Kinerja perlu diukur dalam skenario spesifik Anda. Namun operasi O (n ^ 2) sekarang telah diganti dengan panggilan O (1). Ini adalah metode panggilan virtual yang merupakan lebih lambat dari akses array langsung, sehingga tergantung pada seberapa sering array diputar digunakan setelah rotasi. Jika digunakan sekali, maka pendekatan ini pasti akan menang. Jika diputar kemudian digunakan dalam sistem yang berjalan lama selama berhari-hari, maka rotasi di tempat mungkin berkinerja lebih baik. Itu juga tergantung apakah Anda dapat menerima biaya di muka.

Seperti halnya semua masalah kinerja, ukur, ukur, ukur!

Ini versi yang lebih baik di Jawa: Saya telah membuatnya untuk matriks dengan lebar dan tinggi yang berbeda

• h di sini ketinggian matriks setelah berputar
• w di sini adalah lebar dari matriks setelah berputar

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

Kode ini didasarkan pada posting Nick Berardi.

Cara Ruby: .transpose.map &:reverse

Ada banyak jawaban, dan saya menemukan dua yang mengklaim kompleksitas waktu O (1). The nyata O (1) algoritma adalah untuk meninggalkan penyimpanan array yang tak tersentuh, dan mengubah cara Anda indeks unsur-unsurnya. Tujuannya di sini adalah tidak mengkonsumsi memori tambahan, juga tidak memerlukan waktu tambahan untuk mengulang data.

Rotasi 90, -90 dan 180 derajat adalah transformasi sederhana yang dapat dilakukan selama Anda tahu berapa banyak baris dan kolom dalam array 2D Anda; Untuk memutar vektor apa pun hingga 90 derajat, tukar sumbu dan negasikan sumbu Y. Untuk -90 derajat, tukar sumbu dan meniadakan sumbu X. Untuk 180 derajat, negasikan kedua sumbu tanpa bertukar.

Transformasi lebih lanjut dimungkinkan, seperti mirroring horizontal dan / atau vertikal dengan meniadakan sumbu secara mandiri.

Ini dapat dilakukan melalui misalnya metode accessor. Contoh di bawah ini adalah fungsi JavaScript, tetapi konsepnya berlaku sama untuk semua bahasa.

 // Get an array element in column/row order
 var getArray2d = function(a, x, y) {
   return a[y][x];
 };

 //demo
 var arr = [
   [5, 4, 6],
   [1, 7, 9],
   [-2, 11, 0],
   [8, 21, -3],
   [3, -1, 2]
 ];

 var newarr = [];
 arr[0].forEach(() => newarr.push(new Array(arr.length)));

 for (var i = 0; i < newarr.length; i++) {
   for (var j = 0; j < newarr[0].length; j++) {
     newarr[i][j] = getArray2d(arr, i, j);
   }
 }
 console.log(newarr);

// Get an array element rotated 90 degrees clockwise
function getArray2dCW(a, x, y) {
  var t = x;
  x = y;
  y = a.length - t - 1;
  return a[y][x];
}

//demo
var arr = [
  [5, 4, 6],
  [1, 7, 9],
  [-2, 11, 0],
  [8, 21, -3],
  [3, -1, 2]
];

var newarr = [];
arr[0].forEach(() => newarr.push(new Array(arr.length)));

for (var i = 0; i < newarr[0].length; i++) {
  for (var j = 0; j < newarr.length; j++) {
    newarr[j][i] = getArray2dCW(arr, i, j);
  }
}
console.log(newarr);

// Get an array element rotated 90 degrees counter-clockwise
function getArray2dCCW(a, x, y) {
  var t = x;
  x = a[0].length - y - 1;
  y = t;
  return a[y][x];
}

//demo
var arr = [
  [5, 4, 6],
  [1, 7, 9],
  [-2, 11, 0],
  [8, 21, -3],
  [3, -1, 2]
];

var newarr = [];
arr[0].forEach(() => newarr.push(new Array(arr.length)));

for (var i = 0; i < newarr[0].length; i++) {
  for (var j = 0; j < newarr.length; j++) {
    newarr[j][i] = getArray2dCCW(arr, i, j);
  }
}
console.log(newarr);

// Get an array element rotated 180 degrees
function getArray2d180(a, x, y) {
  x = a[0].length - x - 1;
  y = a.length - y - 1;
  return a[y][x];
}

//demo
var arr = [
  [5, 4, 6],
  [1, 7, 9],
  [-2, 11, 0],
  [8, 21, -3],
  [3, -1, 2]
];

var newarr = [];
arr.forEach(() => newarr.push(new Array(arr[0].length)));

for (var i = 0; i < newarr[0].length; i++) {
  for (var j = 0; j < newarr.length; j++) {
    newarr[j][i] = getArray2d180(arr, i, j);
  }
}
console.log(newarr);

Kode ini mengasumsikan array array bertingkat, di mana setiap array bagian dalam adalah sebuah baris.

Metode ini memungkinkan Anda untuk membaca (atau menulis) elemen (bahkan dalam urutan acak) seolah-olah array telah diputar atau diubah. Sekarang tinggal pilih fungsi yang tepat untuk dipanggil, mungkin dengan referensi, dan pergilah!

Konsep ini dapat diperluas untuk menerapkan transformasi secara aditif (dan non-destruktif) melalui metode accessor. Termasuk rotasi sudut dan penskalaan yang sewenang-wenang.

Beberapa orang telah memasang contoh yang melibatkan pembuatan array baru.

Beberapa hal lain yang perlu dipertimbangkan:

(A) Alih-alih benar-benar memindahkan data, cukup melintasi array "diputar" secara berbeda.

(B) Melakukan rotasi di tempat bisa sedikit rumit. Anda membutuhkan sedikit tempat goresan (mungkin kira-kira sama dengan satu baris atau kolom). Ada sebuah makalah ACM kuno tentang melakukan transpos di tempat ( http://doi.acm.org/10.1145/355719.355729 ), tetapi kode contoh mereka adalah FORTRAN sarat muatan goto.

Tambahan:

http://doi.acm.org/10.1145/355611.355612 adalah algoritma transpos in-place yang dianggap lebih unggul.

Jawaban Nick akan bekerja untuk array NxM juga hanya dengan sedikit modifikasi (sebagai lawan dari 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];

Salah satu cara untuk memikirkan hal ini adalah Anda telah memindahkan bagian tengah sumbu (0,0) dari sudut kiri atas ke sudut kanan atas. Anda hanya memindahkan dari satu ke yang lain.

Waktu - O (N), Spasi - O (1)

public void rotate(int[][] matrix) {
    int n = matrix.length;
    for (int i = 0; i < n / 2; i++) {
        int last = n - 1 - i;
        for (int j = i; j < last; j++) {
            int top = matrix[i][j];
            matrix[i][j] = matrix[last - j][i];
            matrix[last - j][i] = matrix[last][last - j];
            matrix[last][last - j] = matrix[j][last];
            matrix[j][last] = top;
        }
    }
}

Ini versi Ruby saya (perhatikan bahwa nilainya tidak ditampilkan sama, tetapi masih berputar seperti yang dijelaskan).

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

Hasil:

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

inilah metode rotate dalam-ruang, dengan java, hanya untuk persegi. untuk array 2d non-square, Anda harus membuat array baru.

private void rotateInSpace(int[][] arr) {
    int z = arr.length;
    for (int i = 0; i < z / 2; i++) {
        for (int j = 0; j < (z / 2 + z % 2); j++) {
            int x = i, y = j;
            int temp = arr[x][y];
            for (int k = 0; k < 4; k++) {
                int temptemp = arr[y][z - x - 1];
                arr[y][z - x - 1] = temp;
                temp = temptemp;

                int tempX = y;
                y = z - x - 1;
                x = tempX;
            }
        }
    }
}

kode untuk memutar berbagai ukuran array 2d dengan membuat array baru:

private int[][] rotate(int[][] arr) {
    int width = arr[0].length;
    int depth = arr.length;
    int[][] re = new int[width][depth];
    for (int i = 0; i < depth; i++) {
        for (int j = 0; j < width; j++) {
            re[j][depth - i - 1] = arr[i][j];
        }
    }
    return re;
}

Implementasi pseudocode +90 dimple (mis. Transpos lalu balikkan setiap baris) dalam JavaScript:

function rotate90(a){
  // transpose from http://www.codesuck.com/2012/02/transpose-javascript-array-in-one-line.html
  a = Object.keys(a[0]).map(function (c) { return a.map(function (r) { return r[c]; }); });
  // row reverse
  for (i in a){
    a[i] = a[i].reverse();
  }
  return a;
}

Anda dapat melakukan ini dalam 3 langkah mudah :

1 ) Misalkan kita memiliki matriks

   1 2 3
   4 5 6
   7 8 9

2 ) Ambil transpos matriks

   1 4 7
   2 5 8
   3 6 9

3 ) Pertukarkan baris untuk mendapatkan matriks yang diputar

   3 6 9
   2 5 8
   1 4 7

Kode sumber Java untuk ini:

public class MyClass {

    public static void main(String args[]) {
        Demo obj = new Demo();
        /*initial matrix to rotate*/
        int[][] matrix = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };
        int[][] transpose = new int[3][3]; // matrix to store transpose

        obj.display(matrix);              // initial matrix

        obj.rotate(matrix, transpose);    // call rotate method
        System.out.println();
        obj.display(transpose);           // display the rotated matix
    }
}

class Demo {   
    public void rotate(int[][] mat, int[][] tran) {

        /* First take the transpose of the matrix */
        for (int i = 0; i < mat.length; i++) {
            for (int j = 0; j < mat.length; j++) {
                tran[i][j] = mat[j][i]; 
            }
        }

        /*
         * Interchange the rows of the transpose matrix to get rotated
         * matrix
         */
        for (int i = 0, j = tran.length - 1; i != j; i++, j--) {
            for (int k = 0; k < tran.length; k++) {
                swap(i, k, j, k, tran);
            }
        }
    }

    public void swap(int a, int b, int c, int d, int[][] arr) {
        int temp = arr[a][b];
        arr[a][b] = arr[c][d];
        arr[c][d] = temp;    
    }

    /* Method to display the matrix */
    public void display(int[][] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length; j++) {
                System.out.print(arr[i][j] + " ");
            }
            System.out.println();
        }
    }
}

Keluaran:

1 2 3 
4 5 6 
7 8 9 

3 6 9 
2 5 8 
1 4 7 

Ini adalah implementasi saya, dalam kompleksitas memori C, O (1), dalam rotasi tempat, 90 derajat searah jarum jam:

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

Ini adalah versi Java:

public static void rightRotate(int[][] matrix, int n) {
    for (int layer = 0; layer < n / 2; layer++) {
        int first = layer;
        int last = n - 1 - first;
        for (int i = first; i < last; i++) {
           int offset = i - first;
           int temp = matrix[first][i];
           matrix[first][i] = matrix[last-offset][first];
           matrix[last-offset][first] = matrix[last][last-offset];
           matrix[last][last-offset] = matrix[i][last];
           matrix[i][last] = temp;
        }
    }
}

metode pertama-tama memutar lapisan mostouter, kemudian pindah ke lapisan dalam secara kuadrat.

Dari sudut pandang linear, perhatikan matriks:

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

Sekarang ambil A transpose

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

Dan pertimbangkan aksi A 'pada B, atau B pada A'.
Masing-masing:

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

Ini dapat dikembangkan untuk matriks nxn. Dan menerapkan konsep ini dengan cepat dalam kode:

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

Kode C # untuk memutar [n, m] array 2D 90 derajat ke kanan

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

Hasil:

    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

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

Dari PHP5.6, transposisi array dapat dilakukan dengan array_map()panggilan sleak . Dengan kata lain, kolom dikonversi menjadi baris.

Kode: ( Demo )

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

$ dialihkan:

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

For i:= 0 to X do For j := 0 to X do graphic[j][i] := graphic2[X-i][j]

X adalah ukuran dari array grafik.

#transpose adalah metode standar kelas Ruby Array, dengan demikian:

% irb
irb(main):001:0> m = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 0, 1, 2], [3, 4, 5, 6]]
=> [[1, 2, 3, 4], [5, 6, 7, 8], [9, 0, 1, 2], [3, 4, 5, 6]] 
irb(main):002:0> m.reverse.transpose
=> [[3, 9, 5, 1], [4, 0, 6, 2], [5, 1, 7, 3], [6, 2, 8, 4]]

Implementasinya adalah fungsi transposisi n ^ 2 yang ditulis dalam C. Anda dapat melihatnya di sini: http://www.ruby-doc.org/core-1.9.3/Array.html#method-i-transpose dengan memilih "klik untuk beralih sumber "di samping" transpos ".

Saya ingat solusi yang lebih baik daripada O (n ^ 2), tetapi hanya untuk matriks yang dikonstruksi secara khusus (seperti matriks jarang)

Kode C untuk rotasi matriks 90 derajat searah jarum jam DI TEMPAT untuk setiap matriks M * N

void rotateInPlace(int * arr[size][size], int row, int column){
    int i, j;
    int temp = row>column?row:column;
    int flipTill = row < column ? row : column;
    for(i=0;i<flipTill;i++){
        for(j=0;j<i;j++){
            swapArrayElements(arr, i, j);
        }
    }

    temp = j+1;

    for(i = row>column?i:0; i<row; i++){
            for(j=row<column?temp:0; j<column; j++){
                swapArrayElements(arr, i, j);
            }
    }

    for(i=0;i<column;i++){
        for(j=0;j<row/2;j++){
            temp = arr[i][j];
            arr[i][j] = arr[i][row-j-1];
            arr[i][row-j-1] = temp;
        }
    }
}

di sini adalah implementasi In Place saya di C

void rotateRight(int matrix[][SIZE], int length) {

    int layer = 0;

    for (int layer = 0; layer < length / 2; ++layer) {

        int first = layer;
        int last = length - 1 - layer;

        for (int i = first; i < last; ++i) {

            int topline = matrix[first][i];
            int rightcol = matrix[i][last];
            int bottomline = matrix[last][length - layer - 1 - i];
            int leftcol = matrix[length - layer - 1 - i][first];

            matrix[first][i] = leftcol;
            matrix[i][last] = topline;
            matrix[last][length - layer - 1 - i] = rightcol;
            matrix[length - layer - 1 - i][first] = bottomline;
        }
    }
}

Berikut adalah upaya saya untuk rotasi matriks 90 deg yang merupakan solusi 2 langkah dalam C. Pertama transpos matriks di tempat dan kemudian bertukar cols.

#define ROWS        5
#define COLS        5

void print_matrix_b(int B[][COLS], int rows, int cols) 
{
    for (int i = 0; i <= rows; i++) {
        for (int j = 0; j <=cols; j++) {
            printf("%d ", B[i][j]);
        }
        printf("\n");
    }
}

void swap_columns(int B[][COLS], int l, int r, int rows)
{
    int tmp;
    for (int i = 0; i <= rows; i++) {
        tmp = B[i][l];
        B[i][l] = B[i][r];
        B[i][r] = tmp;
    }
}


void matrix_2d_rotation(int B[][COLS], int rows, int cols)
{
    int tmp;
    // Transpose the matrix first
    for (int i = 0; i <= rows; i++) {
        for (int j = i; j <=cols; j++) {
            tmp = B[i][j];
            B[i][j] = B[j][i];
            B[j][i] = tmp;
        }
    }
    // Swap the first and last col and continue until
    // the middle.
    for (int i = 0; i < (cols / 2); i++)
        swap_columns(B, i, cols - i, rows);
}



int _tmain(int argc, _TCHAR* argv[])
{
    int B[ROWS][COLS] = { 
                  {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}
                        };

    matrix_2d_rotation(B, ROWS - 1, COLS - 1);

    print_matrix_b(B, ROWS - 1, COLS -1);
    return 0;
}

@dagorym: Ah, teman. Saya telah menggantung ini sebagai puzzle yang baik "Aku bosan, apa yang bisa saya renungkan". Saya datang dengan kode transposisi di tempat saya, tetapi tiba di sini untuk menemukan Anda cukup identik dengan milikku ... ah, well. Ini dia di 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];
  }
}

Metode C ++ sederhana, bahwa akan ada overhead memori besar dalam array besar.