Jak obrócić tablicę dwuwymiarową?

Zainspirowany postem Raymonda Chena , powiedz, że masz dwuwymiarową tablicę 4x4, napisz funkcję, która obraca ją o 90 stopni. Raymond prowadzi do rozwiązania w pseudo-kodzie, ale chciałbym zobaczyć kilka rzeczy z prawdziwego świata.

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

Staje się:

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

Aktualizacja : odpowiedź Nicka jest najprostsza, ale czy istnieje sposób, aby to zrobić lepiej niż n ^ 2? Co jeśli matryca miała wymiary 10000 x 10000?

Tutaj jest w 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;
}

Czas O (n ^ 2) i algorytm przestrzenny O (1) (bez żadnych obejść i cholernie dziwnych rzeczy!)

Obróć o +90:

1. Transponować
2. Odwróć każdy rząd

Obróć o -90:

Metoda 1:

1. Transponować
2. Odwróć każdą kolumnę

Metoda 2:

1. Odwróć każdy rząd
2. Transponować

Obróć o +180:

Metoda 1 : Obróć dwukrotnie o +90

Metoda 2 : Odwróć każdy wiersz, a następnie odwróć każdą kolumnę (transponuj)

Obróć o -180:

Metoda 1 : Obróć dwukrotnie o -90

Metoda 2 : Odwróć każdą kolumnę, a następnie odwróć każdy wiersz

Metoda 3 : Obróć o +180, ponieważ są one takie same

Chciałbym dodać trochę więcej szczegółów. W tej odpowiedzi kluczowe pojęcia są powtarzane, tempo jest powolne i celowo powtarzalne. Przedstawione tutaj rozwiązanie nie jest najbardziej kompaktowe pod względem składniowym, jest jednak przeznaczone dla tych, którzy chcą dowiedzieć się, czym jest rotacja macierzy i wynikająca z niej implementacja.

Po pierwsze, czym jest matryca? Na potrzeby tej odpowiedzi macierz jest po prostu siatką, w której szerokość i wysokość są takie same. Uwaga: szerokość i wysokość matrycy mogą być różne, ale dla uproszczenia w tym samouczku uwzględniono tylko matryce o równej szerokości i wysokości ( matryce kwadratowe ). I tak, macierze to liczba mnoga macierzy.

Przykładowe macierze to: 2 × 2, 3 × 3 lub 5 × 5. Lub, bardziej ogólnie, N × N. Matryca 2 × 2 będzie miała 4 kwadraty, ponieważ 2 × 2 = 4. Matryca 5 × 5 będzie miała 25 kwadratów, ponieważ 5 × 5 = 25. Każdy kwadrat nazywa się elementem lub wpisem. Będziemy reprezentować każdy element kropką ( .) na poniższych schematach:

Matryca 2 × 2

. .
. .

Matryca 3 × 3

. . .
. . .
. . .

Matryca 4 × 4

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

Co to znaczy obrócić matrycę? Weźmy macierz 2 × 2 i umieśćmy liczby w każdym elemencie, aby można było zaobserwować obrót:

0 1
2 3

Obracanie o 90 stopni daje nam:

2 0
3 1

Dosłownie raz obróciliśmy całą matrycę w prawo, podobnie jak obracanie kierownicy samochodu. Pomóc może „przewrócenie” matrycy na jej prawą stronę. Chcemy napisać w Pythonie funkcję, która pobiera macierz i obraca się raz w prawo. Podpis funkcji będzie:

def rotate(matrix):
    # Algorithm goes here.

Macierz zostanie zdefiniowana za pomocą dwuwymiarowej tablicy:

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

Dlatego pierwsza pozycja indeksu uzyskuje dostęp do wiersza. Druga pozycja indeksu uzyskuje dostęp do kolumny:

matrix[row][column]

Zdefiniujemy funkcję narzędziową do drukowania matrycy.

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

Jedną z metod obracania matrycy jest robienie z niej warstwy na raz. Ale czym jest warstwa? Pomyśl o cebuli. Podobnie jak warstwy cebuli, gdy każda warstwa jest usuwana, przesuwamy się w kierunku środka. Inne analogie to lalka Matryoshka lub gra pass-the-parcel.

Szerokość i wysokość matrycy decydują o liczbie warstw w tej macierzy. Użyjmy różnych symboli dla każdej warstwy:

Matryca 2 × 2 ma 1 warstwę

. .
. .

Matryca 3 × 3 ma 2 warstwy

. . .
. x .
. . .

Matryca 4 × 4 ma 2 warstwy

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

Matryca 5 x 5 ma 3 warstwy

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

Matryca 6 × 6 ma 3 warstwy

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

Matryca 7 × 7 ma 4 warstwy

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

Można zauważyć, że zwiększenie szerokości i wysokości matrycy o jeden nie zawsze zwiększa liczbę warstw. Biorąc powyższe macierze i zestawiając warstwy i wymiary, widzimy, że liczba warstw wzrasta raz na każde dwa przyrosty szerokości i wysokości:

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

Jednak nie wszystkie warstwy wymagają obracania. Macierz 1 × 1 jest taka sama przed i po obrocie. Centralna warstwa 1 × 1 jest zawsze taka sama przed i po obrocie, bez względu na to, jak duża jest ogólna matryca:

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

Biorąc pod uwagę macierz N × N, w jaki sposób możemy programowo określić liczbę warstw, które musimy obrócić? Jeśli podzielimy szerokość lub wysokość przez dwa i zignorujemy resztę, otrzymamy następujące wyniki.

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

Zauważ jak N/2 pasuje liczba warstw, które należy obrócić? Czasami liczba warstw obrotowych jest o jeden mniejsza od całkowitej liczby warstw w matrycy. Dzieje się tak, gdy najbardziej wewnętrzna warstwa jest utworzona tylko z jednego elementu (tj. Matrycy 1 × 1) i dlatego nie musi być obracana. Po prostu zostaje zignorowany.

Niewątpliwie będziemy potrzebować tych informacji w naszej funkcji, aby obrócić macierz, więc dodajmy ją teraz:

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

Teraz wiemy, jakie są warstwy i jak określić liczbę warstw, które faktycznie wymagają obrotu, w jaki sposób izolujemy pojedynczą warstwę, abyśmy mogli ją obrócić? Po pierwsze, sprawdzamy matrycę od zewnętrznej warstwy, do wewnątrz, do wewnętrznej warstwy. Matryca 5 × 5 ma łącznie trzy warstwy i dwie warstwy, które wymagają obrotu:

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

Najpierw spójrzmy na kolumny. Położenie kolumn określających zewnętrzną warstwę, przy założeniu, że liczymy od 0, to 0 i 4:

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

0 i 4 to także pozycje rzędów dla najbardziej zewnętrznej warstwy.

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

Tak będzie zawsze, ponieważ szerokość i wysokość są takie same. Dlatego możemy zdefiniować pozycje kolumny i wiersza warstwy za pomocą tylko dwóch wartości (zamiast czterech).

Przechodząc do drugiej warstwy, pozycje kolumn wynoszą 1 i 3. I tak, zgadliście, to samo dla rzędów. Ważne jest, aby zrozumieć, że musieliśmy zarówno zwiększać, jak i zmniejszać pozycje wierszy i kolumn podczas przechodzenia do wewnątrz do następnej warstwy.

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

Tak więc, aby sprawdzić każdą warstwę, chcemy pętli z licznikami rosnącymi i malejącymi, które reprezentują ruch do wewnątrz, zaczynając od najbardziej zewnętrznej warstwy. Nazwiemy to naszą „pętlą warstw”.

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)

Powyższy kod zapętla pozycje (wierszy i kolumn) dowolnych warstw, które wymagają obrócenia.

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

Mamy teraz pętlę zapewniającą pozycje wierszy i kolumn każdej warstwy. Zmienne firsti lastidentyfikują pozycję indeksu pierwszego i ostatniego wiersza i kolumny. Wracając do naszych tabel wierszy i kolumn:

+--------+-----------+
| 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 | . . . . . |
+-----+-----------+

Możemy więc poruszać się po warstwach matrycy. Teraz potrzebujemy sposobu poruszania się po warstwie, abyśmy mogli przenosić elementy wokół tej warstwy. Uwaga: elementy nigdy nie „przeskakują” z jednej warstwy na drugą, ale poruszają się w obrębie odpowiednich warstw.

Obracanie każdego elementu w warstwie powoduje obrót całej warstwy. Obracanie wszystkich warstw w matrycy powoduje obrót całej matrycy. To zdanie jest bardzo ważne, więc staraj się jak najlepiej je zrozumieć, zanim przejdziesz dalej.

Teraz potrzebujemy sposobu faktycznego przemieszczania elementów, tj. Obracania każdego elementu, a następnie warstwy, a ostatecznie macierzy. Dla uproszczenia powrócimy do matrycy 3x3 - która ma jedną obrotową warstwę.

0 1 2
3 4 5
6 7 8

Nasza pętla warstw zawiera indeksy pierwszej i ostatniej kolumny, a także pierwszego i ostatniego wiersza:

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

Ponieważ nasze macierze są zawsze kwadratowe, potrzebujemy tylko dwóch zmiennych, firsta lastponieważ pozycje indeksu są takie same dla wierszy i kolumn.

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.

Zmienne pierwsza i ostatnia mogą być łatwo wykorzystane do odniesienia do czterech rogów macierzy. Wynika to z faktu, że same rogi można zdefiniować za pomocą różnych kombinacji firsti last(bez odejmowania, dodawania lub przesunięcia tych zmiennych):

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

Z tego powodu rozpoczynamy obrót w czterech zewnętrznych rogach - najpierw je obrócimy. Wyróżnijmy je za pomocą *.

* 1 *
3 4 5
* 7 *

Chcemy zamienić każdy *z *prawej strony. A więc przejdźmy do wydruku naszych narożników zdefiniowanych przy użyciu tylko różnych kombinacji firsti 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)

Dane wyjściowe powinny wynosić:

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

Teraz możemy dość łatwo zamienić każdy z rogów z naszej pętli warstw:

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)

Matryca przed obracaniem narożników:

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

Matryca po obróceniu narożników:

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

Świetny! Z powodzeniem obróciliśmy każdy narożnik matrycy. Ale nie obróciliśmy elementów na środku każdej warstwy. Oczywiście potrzebujemy sposobu iteracji w obrębie warstwy.

Problem polega na tym, że jedyna jak dotąd pętla w naszej funkcji (nasza pętla warstw) przesuwa się do następnej warstwy przy każdej iteracji. Ponieważ nasza matryca ma tylko jedną warstwę obrotową, pętla warstwy wychodzi po obróceniu tylko narożników. Spójrzmy na to, co dzieje się z większą matrycą 5 × 5 (gdzie dwie warstwy wymagają obrotu). Kod funkcji został pominięty, ale pozostaje taki sam jak powyżej:

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)

Dane wyjściowe to:

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

Nie powinno być zaskoczeniem, że rogi zewnętrznej warstwy zostały obrócone, ale można również zauważyć, że rogi kolejnej warstwy (do wewnątrz) również zostały obrócone. To ma sens. Napisaliśmy kod do poruszania się po warstwach, a także do obracania rogów każdej warstwy. To wydaje się postępem, ale niestety musimy cofnąć się o krok. Po prostu przejście do następnej warstwy nie jest dobre, dopóki poprzednia (zewnętrzna) warstwa nie zostanie całkowicie obrócona. To znaczy, dopóki każdy element w warstwie nie zostanie obrócony. Obracanie tylko narożników nie zadziała!

Weź głęboki oddech. Potrzebujemy kolejnej pętli. Zagnieżdżona pętla nie mniej. Nowe zagnieżdżonej pętli użyje firsti lastzmienne, a także przesunięcie poruszać się w warstwie. Tę nową pętlę nazwiemy „pętlą elementów”. Pętla elementów odwiedzi każdy element wzdłuż górnego rzędu, każdy element po prawej stronie, każdy element wzdłuż dolnego rzędu i każdy element po lewej stronie.

• Przesunięcie do przodu wzdłuż górnego wiersza wymaga zwiększenia indeksu kolumny.
• Przesunięcie w dół po prawej stronie wymaga zwiększenia indeksu wierszy.
• Przesunięcie do tyłu wzdłuż dołu wymaga zmniejszenia indeksu kolumny.
• Przesunięcie w górę po lewej stronie wymaga zmniejszenia indeksu wiersza.

Brzmi to skomplikowanie, ale jest to łatwe, ponieważ liczba inkrementacji i dekrementacji w celu osiągnięcia powyższego pozostaje taka sama na wszystkich czterech bokach matrycy. Na przykład:

• Przenieś 1 element w górnym rzędzie.
• Przesuń 1 element w dół po prawej stronie.
• Przesuń 1 element do tyłu wzdłuż dolnego rzędu.
• Przesuń 1 element w górę po lewej stronie.

Oznacza to, że możemy użyć pojedynczej zmiennej w połączeniu ze zmiennymi firsti last, aby poruszać się w warstwie. Warto zauważyć, że poruszanie się w górnym rzędzie i w dół po prawej stronie wymaga zwiększania. Podczas przesuwania się do tyłu wzdłuż dołu i do góry po lewej stronie oba wymagają zmniejszenia.

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)

Teraz musimy po prostu przypisać górę do prawej strony, prawej strony do dołu, od dołu do lewej strony i lewej strony do góry. Łącząc to wszystko, otrzymujemy:

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

Biorąc pod uwagę matrycę:

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

Nasza rotatefunkcja powoduje:

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

Pyton:

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

i przeciwnie do ruchu wskazówek zegara:

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

Jak to działa:

zip(*original)zamieni osie tablic 2d układając odpowiednie elementy z list w nowe listy. ( *Operator mówi funkcji, aby podzieliła zawarte listy na argumenty)

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

Te [::-1]elementy rachunku odwraca array (patrz Rozszerzony plastry czy to pytanie ):

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

Wreszcie połączenie tych dwóch elementów spowoduje transformację obrotu.

Zmiana umieszczenia [::-1]spowoduje odwrócenie list na różnych poziomach matrycy.

Oto taki, który wykonuje obrót w miejscu zamiast używać całkowicie nowej tablicy do przechowywania wyniku. Zrezygnowałem z inicjalizacji tablicy i wydrukowałem ją. Działa to tylko dla tablic kwadratowych, ale mogą mieć dowolny rozmiar. Narzut pamięci jest równy rozmiarowi jednego elementu tablicy, dzięki czemu można wykonać obrót tak dużej tablicy, jak chcesz.

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

Jest tu mnóstwo dobrego kodu, ale chcę tylko pokazać, co się dzieje geometrycznie, aby lepiej zrozumieć logikę kodu. Oto jak do tego podejdę.

po pierwsze, nie należy tego mylić z transpozycją, która jest bardzo łatwa ..

podstawową ideą jest traktowanie jej jak warstw i obracamy jedną warstwę naraz.

powiedzmy, że mamy 4x4

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

po obróceniu go o 90 zgodnie z ruchem wskazówek zegara otrzymujemy

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

więc rozłóżmy to, najpierw obrócimy zasadniczo 4 rogi

1           4


13          16

następnie obracamy następujący diament, który jest trochę krzywo

    2
            8
9       
        15

a następnie drugi przekrzywiony diament

        3
5           
            12
    14

tak, że dba o zewnętrzną krawędź, więc zasadniczo wykonujemy tę powłokę na raz

w końcu środkowy kwadrat (lub jeśli jest dziwny tylko ostatni element, który się nie porusza)

6   7
10  11

więc teraz zastanówmy się nad wskaźnikami każdej warstwy, załóżmy, że zawsze pracujemy z najbardziej zewnętrzną warstwą

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

i tak dalej, aż do połowy krawędzi

więc ogólnie wzór jest

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

Jak powiedziałem w poprzednim poście, oto kod w języku C #, który implementuje obrót macierzy O (1) dla macierzy dowolnego rozmiaru. Dla zwięzłości i czytelności nie ma sprawdzania błędów ani sprawdzania zasięgu. Kod:

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, podniosę rękę, tak naprawdę nie robi żadnych modyfikacji oryginalnej tablicy podczas obracania. Ale w systemie OO nie ma znaczenia, dopóki obiekt wygląda, jakby został obrócony do klientów klasy. W tej chwili klasa Matrix używa odniesień do oryginalnych danych macierzy, więc zmiana dowolnej wartości m1 spowoduje również zmianę m2 i m3. Niewielka zmiana w konstruktorze, aby utworzyć nową tablicę i skopiować do niej wartości, rozwiąże ten problem.

Podczas gdy obracanie danych w miejscu może być konieczne (być może w celu zaktualizowania fizycznie przechowywanej reprezentacji), staje się łatwiejsze i być może bardziej wydajne, aby dodać warstwę pośrednią do dostępu do tablicy, być może interfejs:

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

Jeśli Matrixjuż implementujesz ten interfejs, możesz go obrócić za pomocą klasy dekoratora, takiej jak ta:

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

Obracanie o + 90 / -90 / 180 stopni, obracanie w poziomie / w pionie i skalowanie można również osiągnąć w ten sposób.

Wydajność musiałaby być mierzona w konkretnym scenariuszu. Jednak operacja O (n ^ 2) została teraz zastąpiona wywołaniem O (1). Jest to wirtualne wywołanie metody, które jest wolniejsze niż bezpośredni dostęp do tablicy, więc zależy od tego, jak często obrócona tablica jest używana po rotacji. Jeśli zastosuje się go raz, to podejście na pewno by wygrało. Jeśli jest obrócony, a następnie używany przez długi czas w systemie, rotacja w miejscu może działać lepiej. Zależy to również od tego, czy możesz zaakceptować koszty początkowe.

Podobnie jak w przypadku wszystkich problemów z wydajnością, mierz, mierz, mierz!

To lepsza wersja w Javie: Zrobiłem to dla matrycy o innej szerokości i wysokości

• h jest tutaj wysokością matrycy po obróceniu
• w oznacza tutaj szerokość matrycy po obróceniu

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

Ten kod oparty jest na poście Nicka Berardi.

Rubinowy sposób: .transpose.map &:reverse

Jest już wiele odpowiedzi i znalazłem dwie twierdzące, że złożoność czasowa O (1). rzeczywistym O (1) algorytm jest pozostawienie przechowywanie tablicy nietknięte i zmienić sposób wskaźnik jego elementy. Chodzi tutaj o to, aby nie zużywał dodatkowej pamięci ani nie wymagał dodatkowego czasu na iterację danych.

Obracanie o 90, -90 i 180 stopni to proste transformacje, które można wykonać, o ile wiesz, ile wierszy i kolumn znajduje się w tablicy 2D; Aby obrócić dowolny wektor o 90 stopni, zamień osie i neguj oś Y. Dla -90 stopni zamień osie i neguj oś X. Dla 180 stopni neguj obie osie bez zamiany.

Możliwe są dalsze przekształcenia, takie jak odbicie lustrzane w poziomie i / lub w pionie poprzez niezależne negowanie osi.

Można tego dokonać np. Metodą akcesora. Poniższe przykłady to funkcje JavaScript, ale pojęcia dotyczą jednakowo wszystkich języków.

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

Ten kod zakłada tablicę zagnieżdżonych tablic, przy czym każda tablica wewnętrzna jest rzędem.

Ta metoda umożliwia odczytywanie (lub zapisywanie) elementów (nawet w losowej kolejności), tak jakby tablica została obrócona lub przekształcona. Teraz wystarczy wybrać odpowiednią funkcję do wywołania, prawdopodobnie przez odniesienie, i gotowe!

Pojęcie to można rozszerzyć, aby zastosować transformacje w sposób addycyjny (i nieniszczący) za pomocą metod akcesorów. W tym dowolne obroty kątów i skalowanie.

Kilka osób już podało przykłady, które wymagają stworzenia nowej tablicy.

Kilka innych rzeczy do rozważenia:

(a) Zamiast faktycznie przenosić dane, po prostu przejdź w inny sposób do „obróconej” tablicy.

(b) Wykonanie obrotu w miejscu może być nieco trudniejsze. Potrzebujesz trochę miejsca na zarysowania (prawdopodobnie mniej więcej równego rozmiarowi jednego wiersza lub kolumny). Istnieje starożytna praca ACM na temat dokonywania transpozycji w miejscu ( http://doi.acm.org/10.1145/355719.355729 ), ale ich przykładowy kod to paskudny fortuna z ładunkiem.

Uzupełnienie:

http://doi.acm.org/10.1145/355611.355612 to kolejny, podobno lepszy, lokalny algorytm transpozycji.

Odpowiedź Nicka działałaby również na macierz NxM z niewielką modyfikacją (w przeciwieństwie do 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];

Jednym ze sposobów myślenia o tym jest przeniesienie środka osi (0,0) z lewego górnego rogu do prawego górnego rogu. Po prostu transponujesz z jednego na drugi.

Czas - O (N), Spacja - 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;
        }
    }
}

Oto moja wersja Ruby (zauważ, że wartości nie są wyświetlane tak samo, ale wciąż się obraca zgodnie z opisem).

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

Wyjście:

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

oto metoda rotacji w przestrzeni, według java, tylko dla kwadratu. w przypadku nie kwadratowej tablicy 2d i tak będziesz musiał utworzyć nową tablicę.

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

kod, aby obrócić tablicę 2d dowolnego rozmiaru, tworząc nową tablicę:

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

Implementacja pseudokodu +90 dołka (np. Transpozycja, a następnie odwrócenie każdego wiersza) w 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;
}

Możesz to zrobić w 3 prostych krokach :

1 ) Załóżmy, że mamy matrycę

   1 2 3
   4 5 6
   7 8 9

2 ) Weź transpozycję macierzy

   1 4 7
   2 5 8
   3 6 9

3 ) Zamień rzędy, aby uzyskać obróconą matrycę

   3 6 9
   2 5 8
   1 4 7

Kod źródłowy Java dla tego:

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

Wynik:

1 2 3 
4 5 6 
7 8 9 

3 6 9 
2 5 8 
1 4 7 

To jest moja implementacja, w złożoności pamięci C, O (1), w miejscu obrotu, 90 stopni w prawo:

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

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

metoda najpierw obraca najbardziej rutynową warstwę, a następnie przechodzi do warstwy wewnętrznej pośrodku.

Z liniowego punktu widzenia rozważmy macierze:

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

Teraz weź transpozycję A

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

I rozważ działanie A 'na B lub B na A'.
Odpowiednio:

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

Można to rozszerzyć dla dowolnej macierzy nxn. I szybkie zastosowanie tej koncepcji w kodzie:

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

Kod C # do obracania [n, m] Tablice 2D o 90 stopni w prawo

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

Wynik:

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

Od PHP 5.6 transpozycja macierzy może być wykonywana za pomocą eleganckiego array_map()wywołania. Innymi słowy, kolumny są konwertowane na wiersze.

Kod: ( Demo )

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

$ transponowane:

[
    [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 to rozmiar tablicy, w której znajduje się grafika.

#transpose jest standardową metodą klasy Ruby's Array, a zatem:

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

Implementacja jest funkcją transpozycji n ^ 2 napisaną w C. Możesz ją zobaczyć tutaj: http://www.ruby-doc.org/core-1.9.3/Array.html#method-i-transpose wybierając „kliknij przełączać źródło „obok” transpozycji ”.

Pamiętam rozwiązania lepsze niż O (n ^ 2), ale tylko dla specjalnie skonstruowanych matryc (takich jak matryce rzadkie)

Kod C dla obrotu matrycy o 90 stopni w prawo W MIEJSCU dla dowolnej matrycy 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;
        }
    }
}

oto moja implementacja In Place w 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;
        }
    }
}

Oto moja próba rotacji matrycy o 90 stopni, która jest 2-etapowym rozwiązaniem w C. Najpierw transponuj matrycę na miejsce, a następnie zamień 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: Aw, stary. Trzymałem się tego jako dobrej łamigłówki „Jestem znudzony, co mogę rozważać”. Wymyśliłem swój lokalny kod transpozycji, ale dotarłem tutaj, by znaleźć twój prawie identyczny z moim ... och, cóż. Tutaj jest w 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];
  }
}

Prosta metoda C ++, ponieważ w dużej tablicy byłby duży narzut pamięci.