螺旋循环 | Baeldung中文网

1. Overview

In this tutorial, we’ll study an algorithm for traversing the elements of a matrix in a square spiral.

2. What Is a Spiral?

A spiral is a curve that originates from a point called the center and progressively gets farther as it winds around it. In a polar plane, a spiral has the form of a continuous monotonic function that relates the angle $\theta$ to the radius , as $r = f(\theta)$ . This is the graph of one of the most common spirals, the spiral of Archimedes:

spiral continuous

Generalized algorithms for computing spirals that extend over surfaces with arbitrary shapes also exist. For looping over matrices, however, a slightly different definition is needed.

3. Spirals and Matrices

In relation to matrices, the spiral that loops over its elements is called a square spiral. A square spiral has this shape:

square spiral

Because we can’t define it as a continuous function, we can instead define it procedurally. It’s intuitive to understand how it functions, if we imagine traversing a matrix in a spiral fashion starting from one of its elements. Let’s use this sample matrix:

$\begin{bmatrix} e_{1,1} & e_{1,2} & e_{1,3} \\ e_{2,1} & e_{2,2} & e_{2,3} \\ e_{3,1} & e_{3,2} & e_{3,3} \\ \end{bmatrix}$

We can indicate with numbers the order in which the elements have to be traversed, starting from 1, to produce a square spiral. Traversing the matrix in spiral then corresponds to vectorizing it by starting from one corner and looping over all elements, and then terminating in the center:

$\begin{matrix} \text{Clockwise} & \text{Counter-clockwise} \\ \text{traversal} & \text{traversal} \\ \begin{bmatrix} 1 & 2 & 3 \\ 8 & 9 & 4 \\ 7 & 6 & 5 \\ \end{bmatrix} & \begin{bmatrix} 1 & 8 & 7 \\ 2 & 9 & 6 \\ 3 & 4 & 5 \\ \end{bmatrix} \end{matrix}$

Or, alternatively, by starting from the center and then terminating in one of the corners:

$\begin{matrix} \text{Clockwise} & \text{Counter-clockwise} \\ \text{traversal} & \text{traversal} \\ \begin{bmatrix} 9 & 2 & 3 \\ 8 & 1 & 4 \\ 7 & 6 & 5 \\ \end{bmatrix} & \begin{bmatrix} 9 & 8 & 7 \\ 2 & 1 & 6 \\ 3 & 4 & 5 \\ \end{bmatrix} \end{matrix}$

The traversal occurs by moving in one direction by steps, then rotating, then moving more steps, then rotating, then incrementing the counter i:= i+1 and repeating. Notice also how the traversal from the center to the corner is simply a reversal of the traversal, and that this is valid for both clockwise and counter-clockwise spirals.

4. Non-Square Matrix

If the matrix is non-square, and has rows and columns, such that $N>M \vee M>N$ , then we’ll need some extra steps. We’ll first extend it to the square matrix of size $A_{P, P}: P ={max}(N, M)$ , and then skip all elements that are present in the square but not in the rectangular matrix:

$\begin{matrix} \text{3 by 5 Spiral} \\ \begin{pmatrix}\O & \O & \O & \O & \O \end{pmatrix}\\ \begin{bmatrix} 15 & 9 & 2 & 3 & 10\\ 14 & 8 & 1 & 4 & 11\\ 13 & 7 & 6 & 5 & 12\\ \end{bmatrix}\\ \begin{pmatrix}\O & \O & \O & \O & \O \end{pmatrix} \end{matrix}$

We’re now going to study the algorithm that performs this traversal. One last note before that: instead of using rows and columns as a coordinate system, it’s more practical to shift the origin to the center of the matrix. This means that, if and are odd, we place the origin (0; 0) to $( \frac{N+1}{2}; \frac{M+1}{2} )$ :

grid

4. Traversing From Center to Corner

We can now study an algorithm that traverses the matrix from the origin (0; 0) , up to the corner $(-\frac{N+1}{2}; -\frac{M+1}{2})$ , in a square spiral. To build one, we need to define two pointers x, y that store the coordinates of the current element relative to the center, and two direction vectors $dx, dy = \pm 1$ . The algorithm is this:

algorithm ClockwiseSquareSpiral(N, M, A):
    // INPUT
    //    N = the number of rows in the matrix
    //    M = the number of columns in the matrix
    //    A = the matrix to traverse
    // OUTPUT
    //    Traverses the matrix A from the center to the corner in a clockwise spiral
    
    x <- 0
    y <- 0
    dx <- 0
    dy <- -1
    
    for i <- 0 to (max(N, M))^2:
        if -N/2 < x <= N/2 and -M/2 < y <= M/2:
            a[x, y] is in A, so we do something with it
        if x = y or (x = -y and x < 0) or (x = 1 - y and x > 0):
            // End of current segment, rotate direction
            temp <- dx
            dx <- -dy
            dy <- temp
        x <- x + dx
        y <- y + dy

When executed on a 3 by 5 matrix, as in the example above, the algorithm produces the traversal in the expected order:

output MiLSsl

We can also define a counter-clockwise rotation, by simply modifying slightly the second if statement:

algorithm CounterClockwiseSquareSpiral(N, M, A):
    // INPUT
    //    N = the number of rows in the matrix
    //    M = the number of columns in the matrix
    //    A = the matrix to traverse
    // OUTPUT
    //    Traverses the matrix A from the center to the corner in a counter-clockwise spiral
    
    x <- 0
    y <- 0
    dx <- 0
    dy <- 1
    
    for i <- 0 to (max(N, M))^2:
        if -N/2 < x <= N/2 and -M/2 < y <= M/2: 
            // a[x, y] is in A, so we do something with it
        if (x = -y) or (x = y and x > 0) or (x = -1 + y and x < 0):
            // End of current segment, rotate direction
            temp <- dx
            dx <- dy
            dy <- -temp
        x <- x + dx
        y <- y + dy

And as expected, this is the output with a 3 by 7 matrix:

output fw6osf1

5. Traversing from Corner to Center

If we want instead to traverse the matrix from a corner to the center, we can refer to the consideration we made above. All that we need to do is to store in a list the order of traversal and then reverse it.

For example, this is the reverse spiral traversal of a 5 by 7 matrix:

reverse1

6. Conclusion

In this article, we studied how to loop over the elements of a matrix in a square spiral pattern.

Persistence

REST

Security