Матрица и алгоритм "спираль"

Question

Я хотел спросить, есть ли какой-нибудь готовый алгоритм, который позволил мне сделать это: у меня есть матрица m (col) x n (строка) с m x n элементами. Я хочу дать положение этому элементу, начиная с центра и вращаясь по спирали, например, для матрицы 3x3 у меня 9 элементов, определенных таким образом:

 5  6  7
 4  9  8
 3  2  1 

или для матрицы 4 x 3 у меня 12 элементов, определите:

  8   9  10  1
  7  12  11  2
  6   5   4  3

или снова, матрица 5x2 у меня есть 10 элементов, определенных таким образом:

    3  4
    7  8
   10  9
    6  5 
    2  1

и т.д.. Я решил, в основном, определить массив целых чисел m x n элементов и загрузить вручную значение, но в общем случае для меня такая матрица автоматически формируется из алгоритма. Спасибо, кто может помочь мне найти что-то так, большое спасибо.

UPDATE

Этот код точно соответствует тому, что я хочу иметь, но не в Delphi; только мне нужно, чтобы это начиналось с 1, а не с 0. Для меня важно то, что оно действительно для любых матриц m x n. Кто поможет мне перевести это на delphi?

(defun spiral (rows columns)  
  (do ((N (* rows columns))       
    (spiral (make-array (list rows columns) :initial-element nil))      
    (dx 1) (dy 0) (x 0) (y 0)    
   (i 0 (1+ i)))     
 ((= i N) spiral)   
 (setf (aref spiral y x) i)
    (let ((nx (+ x dx)) (ny (+ y dy)))  
    (cond       
       ((and (< -1 nx columns)       
       (< -1 ny rows)           
       (null (aref spiral ny nx)))    
    (setf x nx 
          y ny))  
     (t (psetf dx (- dy)                 
       dy dx)       
    (setf x (+ x dx)             
     y (+ y dy))))))) 


> (pprint (spiral 6 6))

#2A ((0  1  2  3  4  5)
    (19 20 21 22 23  6)
    (18 31 32 33 24  7)
    (17 30 35 34 25  8)
    (16 29 28 27 26  9)
    (15 14 13 12 11 10))


> (pprint (spiral 5 3))

#2A  ((0  1 2)
     (11 12 3)
     (10 13 4)
      (9 14 5)
      (8 7 6))

Еще раз большое спасибо.

Answer 1

На основе классического спирального алгоритма .вспомогательная неквадратная матрица:

program SpiralMatrix;
{$APPTYPE CONSOLE}
uses
  SysUtils;

type
  TMatrix = array of array of Integer;

procedure PrintMatrix(const a: TMatrix);
var
  i, j: Integer;
begin
  for i := 0 to Length(a) - 1 do
  begin
    for j := 0 to Length(a[0]) - 1 do
      Write(Format('%3d', [a[i, j]]));
    Writeln;
  end;
end;

var
  spiral: TMatrix;
  i, m, n: Integer;
  row, col, dx, dy,
  dirChanges, visits, temp: Integer;
begin
  m := 3; // columns
  n := 3; // rows
  SetLength(spiral, n, m);
  row := 0;
  col := 0;
  dx := 1;
  dy := 0;
  dirChanges := 0;
  visits := m;
  for i := 0 to n * m - 1 do
  begin
    spiral[row, col] := i + 1;
    Dec(visits);
    if visits = 0 then
    begin
      visits := m * (dirChanges mod 2) + n * ((dirChanges + 1) mod 2) - (dirChanges div 2) - 1;
      temp := dx;
      dx := -dy;
      dy := temp;
      Inc(dirChanges);
    end;
    Inc(col, dx);
    Inc(row, dy);
  end;
  PrintMatrix(spiral);
  Readln;
end.

3 x 3:

1  2  3
8  9  4
7  6  5

4 x 3:

 1  2  3  4
10 11 12  5
 9  8  7  6

2 x 5:

 1  2
10  3
 9  4
 8  5
 7  6

Answer 2

Вот, пожалуйста! После 30 некоторых синтаксических ошибок ...

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

Я добавил несколько комментариев в код. Достаточно понять большую часть этого. Основную навигационную систему немного сложнее объяснить. Вкратце, выполнение спирали происходит в первом направлении 1 раз, во втором 1 раз, третьем 2 раза, четвертом 2 раза, пятом 3 раза, 3, 4, 4, 5, 5 и так далее. Я использую то, что я назвал seed и step, чтобы получить такое поведение.

program test;

var
    w, h, m, n, v, d : integer; // Matrix size, then position, then value and direction.
    spiral : array of array of integer; // Matrix/spiral itself.
    seed, step : integer; // Used to travel the spiral.

begin
    readln(h);
    readln(w);
    setlength(spiral, h, w);
    v := w * h; // Value to put in spiral.
    m := trunc((h - 1) / 2);  // Finding center.
    n := trunc((w - 1) / 2);
    d := 0; // First direction is right.

    seed := 2;
    step := 1;

    // Travel the spiral.
    repeat
        // If in the sub-spiral, store value.
        if ((m >= 0) and (n >= 0) and (m < h) and (n < w)) then
        begin
            spiral[m, n] := v;
            v := v - 1;
        end;

        // Move!
        case d of
            0: n := n + 1;
            1: m := m - 1;
            2: n := n - 1;
            3: m := m + 1;
        end;

        // Plan trajectory.
        step := step - 1;
        if step = 0 then
        begin
            d := (d + 1) mod 4;
            seed := seed + 1;
            step := trunc(seed / 2);
        end;
    until v = 0;

    // Print the spiral.
    for m := 0 to (h - 1) do
    begin
        for n := 0 to (w - 1) do
        begin
            write(spiral[m, n], ' ');
        end;
        writeln();
    end;

end.

Если вам это действительно нужно для печати текстовых спиралей, я позволю вам выровнять цифры. Просто заполните их пробелами.

EDIT:

Забыл ... Чтобы заставить его работать на ideone, я поместил параметры в 2 строки в качестве входных данных. м, то n.

Например:

5
2

выходы * * тысяча двадцать-одны

3 4 
7 8 
10 9 
6 5 
2 1 

Answer 3

Несмотря на то, что на вопрос уже дан ответ, это альтернативное решение (возможно, более простое). Решение в Python (с использованием NumPy для двухсторонних массивов), но может быть легко перенесено.

Основная идея состоит в том, чтобы использовать тот факт, что число шагов известно (m * n) как конечное условие, и правильно вычислять следующий элемент цикла на каждой итерации:

import numpy as np

def spiral(m, n):
    """Return a spiral numpy array of int with shape (m, n)."""
    a = np.empty((m, n), int)
    i, i0, i1 = 0, 0, m - 1
    j, j0, j1 = 0, 0, n - 1
    for k in range(m * n):
        a[i, j] = k
        if   i == i0 and     j0 <= j <  j1: j += 1
        elif j == j1 and     i0 <= i <  i1: i += 1
        elif i == i1 and     j0 <  j <= j1: j -= 1
        elif j == j0 and 1 + i0 <  i <= i1: i -= 1
        else:
            i0 += 1
            i1 -= 1
            j0 += 1
            j1 -= 1
            i, j = i0, j0
    return a

А вот некоторые выводы:

>>> spiral(3,3)
array([[0, 1, 2],
       [7, 8, 3],
       [6, 5, 4]])
>>> spiral(4,4)
array([[ 0,  1,  2,  3],
       [11, 12, 13,  4],
       [10, 15, 14,  5],
       [ 9,  8,  7,  6]])
>>> spiral(5,4)
array([[ 0,  1,  2,  3],
       [13, 14, 15,  4],
       [12, 19, 16,  5],
       [11, 18, 17,  6],
       [10,  9,  8,  7]])
>>> spiral(2,5)
array([[0, 1, 2, 3, 4],
       [9, 8, 7, 6, 5]])

Answer 4

Вот прокомментированная реализация JavaScript для того, чего вы пытаетесь достичь.

// return an array representing a matrix of size MxN COLxROW
function spiralMatrix(M, N) {
var result = new Array(M * N);
var counter = M * N;
// start position
var curCol = Math.floor((M - 1) / 2);
var curRow = Math.floor(N / 2);
// set the center
result[(curRow * M) + curCol] = counter--;
// your possible moves RIGHT, UP, LEFT, DOWN * y axis is flipped
var allMoves = [[1,0], [0,-1], [-1,0], [0,1]];
var curMove = 0;
var moves = 1; // how many times to make current Move, 1,1,2,2,3,3,4,4 etc
// spiral
while(true) {
 for(var i = 0; i < moves; i++) {
  // move in a spiral outward counter clock-wise direction
  curCol += allMoves[curMove][0];
  curRow += allMoves[curMove][1];
  // naively skips locations that are outside of the matrix bounds
  if(curCol >= 0 && curCol < M && curRow >= 0 && curRow < N) {
   // set the value and decrement the counter
   result[(curRow * M) + curCol] = counter--;
   // if we reached the end return the result
   if(counter == 0) return result;
  }
 }
 // increment the number of times to move if necessary UP->LEFT and DOWN->RIGHT
 if(curMove == 1 || curMove == 3) moves++;
 // go to the next move in a circular array fashion
 curMove = (curMove + 1) % allMoves.length;
}
}

Код не самый эффективный, потому что он идет по спирали наивно, не проверив сначала, находится ли место, по которому идетявляется действительным.Он только проверяет действительность текущего местоположения прямо перед тем, как попытаться установить значение для него.