矩阵和算法“螺旋”

Question

矩阵和算法“螺旋”

8

我想询问是否有现成的算法，可以满足以下需求：我有一个 m 列 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个元素：

我已经基本解决了定义一个m x n个整数数组并手动加载值的问题，但是对于由算法自动创建的矩阵来说，像那样的东西对我来说也很重要。

谢谢能帮助我找到这样东西的人，非常感谢。

更新

这段代码完全符合我的要求，但不是用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))

再次非常感谢。

- Marcello Impastato

4

在我看来，你的算法还没有明确定义。我期望5x2矩阵应为((6 7) (5 8) (4 9) (3 10) (2 1))。 - David Heffernan

2

我和David在一起。为什么1的起点位置不同？应该每次都是相同的角落。 - Chris Thornton

4

我不理解你的算法，它并不一致。例如3x3的经典螺旋算法应该是：(1 2 3)(8 9 4)(7 6 5)。在这里看看。 - kobik

2

你好，很可能我没有正确地表达“螺旋”。这只是为了给出一个想法，在矩阵中放置数字时设计成螺旋形式，例如对于6个数字，它从6到1开始：6、5、4、3、2、1。元素6位于矩阵的中心，矩阵的索引按螺旋形式从左到右旋转。根据示例所示有相应结果。再次请原谅我的糟糕英语。将此元素设置的矩阵应用于随机数。 - Marcello Impastato

3

可以先从这个链接开始查看：http://www.technicalinterviewquestions.net/2009/03/print-2d-array-matrix-spiral-order.html。 - A Lombardo

显示剩余15条评论

4个回答

1

搞定了！经过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上运行，我将参数分为两行输入。先输入m，然后是n。

例如：

5
2

产生。

- Joanis

1

非常感谢你Joanis。这个解决方案就是我所寻找的，它工作得非常非常好。再次感谢；也感谢所有其他帮助过我的人。 - Marcello Impastato

当我使用2x2和4x3进行测试时，它产生了一些奇怪的螺旋。 - kobik

@kobik：是的，并非所有情况都能称作螺旋状。中心点由 floor((height-1)/2) 和 floor((width-1)/2) 定义，而且方向序列从“右”开始，然后是“上”……这就解释了奇怪的非螺旋形状。2x2 的中心点为 (0, 0)=4，然后移动到 (0, 1)=3，直到此时还有些“道理”，但接下来我们必须走向上方，可上方没有数字，所以我们转而向左，返回原地，然后在第二行继续螺旋：2，1。这就是为什么 2x2 的结果会像 (4 3) (2 1) 这样奇怪的原因。 - Joanis

-1

这是您尝试实现的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;
}
}

代码不是最有效的，因为它朴素地遍历螺旋线而没有首先检查它正在遍历的位置是否有效。它仅在尝试设置其值之前检查当前位置的有效性。

- Louis Ricci

-1

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

- joanpau

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- kobik · Accepted Answer

基于经典的螺旋算法，支持非方阵矩阵:

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: