矩阵和算法“螺旋”

Question

我想问是否有一些算法准备好，允许我这样做：我有一个矩阵 m (col) xn (row) 与 mxn 元素。我想给这个元素从中心开始并以螺旋形式旋转的位置，例如，对于 3x3 矩阵，我有 9 个元素，这样定义：

 5  6  7
 4  9  8
 3  2  1 

或者对于 una 矩阵 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

等等。 我已经解决了基本上定义 mxn 元素的整数数组并手动加载值的问题，但对我来说，就像自动由算法生成的矩阵一样。 感谢谁能帮我找到一些东西，非常感谢。

更新

这段代码，完全符合我想要的，但不是在delphi中；只是我需要从 1 开始，而不是从 0 开始。对我来说重要的是它对任何矩阵 mx 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 次，依此类推。我使用所谓的“种子”和“步骤”来获得此行为。

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.

如果您确实需要它来打印文本螺旋，我会让您对齐数字。只需用空格填充它们即可。

编辑：

忘记了......为了使其在 ideone 上工作，我将参数放在 2 行上作为输入。 m，然后n。

例如：

5
2

产量

3 4 
7 8 
10 9 
6 5 
2 1 

Answer 3

以下是您想要完成的任务的带注释的 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;
}
}

该代码不是最有效的，因为它天真地沿着螺旋走，而没有首先检查它所走的位置是否有效。它仅在尝试设置值之前检查当前位置的有效性。

Answer 4

尽管问题已经得到解答，但这是一种替代解决方案（可以说更简单）。
解决方案是在 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]])