呈螺旋状循环
一位朋友需要一种算法,可以让他循环遍历 NxM 矩阵(N 和 M 是奇数)的元素。 我想出了一个解决方案,但我想看看我的 SO'ers 同胞是否能想出更好的解决方案。
我将发布我的解决方案作为该问题的答案。
示例输出:
对于 3x3 矩阵,输出应为:
(0, 0) (1, 0) (1, 1) (0, 1) (-1, 1) (-1, 0) (-1,-1) (0, -1) (1, -1)
此外,该算法应该支持非方阵,例如对于 5x3 矩阵,输出应该是:
(0, 0) (1, 0) (1, 1) (0, 1) (-1, 1) (-1, 0) (-1,-1) (0, -1) (1, -1) (2, -1) (2, 0) (2, 1) (-2, 1) (-2, 0) (-2, -1)
A friend was in need of an algorithm that would let him loop through the elements of an NxM matrix (N and M are odd). I came up with a solution, but I wanted to see if my fellow SO'ers could come up with a better solution.
I'm posting my solution as an answer to this question.
Example Output:
For a 3x3 matrix, the output should be:
(0, 0)
(1, 0)
(1, 1)
(0, 1)
(-1, 1)
(-1, 0)
(-1, -1)
(0, -1)
(1, -1)
Furthermore, the algorithm should support non-square matrices, so for example for a 5x3 matrix, the output should be:
(0, 0)
(1, 0)
(1, 1)
(0, 1)
(-1, 1)
(-1, 0)
(-1, -1)
(0, -1)
(1, -1)
(2, -1)
(2, 0)
(2, 1)
(-2, 1)
(-2, 0)
(-2, -1)
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(30)
我和一位朋友一起制作了这个,他在 Javascript 上调整了画布的螺旋长宽比。 我得到的最佳解决方案是图像逐像素演化,填充整个图像。
希望它对某人有所帮助。
您可以看到它在 http://jsfiddle.net/hitbyatruck/c4Kd6/ 上运行。 只需确保更改 JavaScript 变量和 HTML 属性上画布的宽度和高度。
I made this one with a friend that adjusts the spiral to the canvas aspect ratio on Javascript. Best solution I got for a image evolution pixel by pixel, filling the entire image.
Hope it helps some one.
You can see it working on http://jsfiddle.net/hitbyatruck/c4Kd6/ . Just be sure to change the width and height of the canvas on the javascript vars and on the attributes on the HTML.
只是为了 Javascript 的乐趣:
Just for fun in Javascript:
我正在分享这段我为不同目的而设计的代码; 它是关于查找数组元素@螺旋索引“index”的列号“X”和行号“Y”。 该函数采用矩阵的宽度“w”和高度“h”以及所需的“索引”。 当然,这个函数可以用来产生相同的所需输出。 我认为这是最快的方法(因为它跳过单元格而不是扫描它们)。
I am sharing this code which I designed for a different purpose; it is about finding the Column number "X", and the row number "Y" of array element @ spiral index "index". This function takes the width "w" and height "h" of the matrix, and the required "index". Of course, this function can be used to produce the same required output. I think it is the fastest possible method (as it jumps over cells instead of scanning them).
Python 使用 Can Berk Güder 回答 循环顺时针螺旋代码。
Python looping clockwise spiral code using Can Berk Güder answer.
Davidont 在 VB.Net 中的优秀解决方案
Davidont's excellent solution in VB.Net
这是我的解决方案(Python):
Here's my solution (in Python):
C++ 有人吗? 来自 python 的快速翻译,为了完整性而发布
C++ anyone? Quick translation from python, posted for completeness
对于这个问题,已经有许多用各种编程语言编写的解决方案,但它们似乎都源于相同的复杂方法。 我将考虑计算螺旋的更普遍的问题,可以使用归纳法简洁地表达它。
基本情况:从 (0, 0) 开始,向前移动 1 格,向左转,向前移动 1 格,向左转。
归纳步骤:向前移动n+1格,左转,向前移动n+1格,左转。
表达这个问题的数学优雅强烈表明应该有一个简单的算法来计算解决方案。 考虑到抽象,我选择不使用特定的编程语言来实现该算法,而是以伪代码的形式实现。
首先,我将考虑一种使用 4 对 while 循环仅计算螺旋的 2 次迭代的算法。 每对的结构相似,但其本身又不同。 一开始这可能看起来很疯狂(有些循环只执行一次),但我将逐步进行转换,直到我们到达 4 对相同的循环,因此可以用放置在另一个循环内的一对循环替换。
这将为我们提供一个无需使用任何条件即可计算 n 次迭代的通用解决方案。
我们要做的第一个转换是引入一个新变量 d(表示方向),其值可以是 +1 或 -1。 方向在每对循环之后切换。 由于我们知道所有点上 d 的值,因此我们可以将每个不等式的每一边都乘以它,相应地调整不等式的方向,并将 d 与一个常数的乘法简化为另一个常数。 这给我们留下了以下内容。
现在我们注意到 x * d 和 RHS 都是整数,因此我们可以从 RHS 中减去 0 到 1 之间的任何实数值,而不会影响不等式的结果。 我们选择从每隔一对 while 循环的不等式中减去 0.5,以便建立更多的模式。
现在我们可以引入另一个变量 m 来表示每对 while 循环所采取的步数。
最后,我们看到每对 while 循环的结构是相同的,并且可以简化为放置在另一个循环内部的单个循环。 另外,为了避免使用实数值,我乘以 m 的初始值; m 值增加; 每个不等式两边都除以 2。
这导致了本答案开头所示的解决方案。
编辑:已经过去几年了,但我遇到了类似的问题,并在 F# 中编写了以下解决方案,我想分享。 在我原来的答案中,“打印”一词可能用词不当,但希望这个非伪代码版本能够解决有关多功能性和终止条件的评论中提出的任何观点。 我添加了关于任意点螺旋式旋转的示例用例,并找到迭代 NxM 矩阵的原始问题的正确解决方案。
There have been many proposed solutions for this problem wrote in various programming languages however they all seem to stem from the same convoluted approach. I'm going to consider the more general problem of computing a spiral which can be expressed concisely using induction.
Base case: Start at (0, 0), move forward 1 square, turn left, move forward 1 square, turn left.
Inductive step: Move forward n+1 squares, turn left, move forward n+1 squares, turn left.
The mathematical elegance of expressing this problem strongly suggests there should be a simple algorithm to compute the solution. Keeping abstraction in mind, I've chosen not to implement the algorithm in a specific programming language but rather as pseudo-code.
First I'll consider an algorithm to compute just 2 iterations of the spiral using 4 pairs of while loops. The structure of each pair is similar, yet distinct in its own right. This may seem crazy at first (some loops only get executed once) but step by step I'll make transformations until we arrive at 4 pairs of loops that are identical and hence can be replaced with a single pair placed inside of another loop.
This will provide us with a general solution of computing n iterations without using any conditionals.
The first transformation we will make is the introduction of a new variable d, for direction, that holds either the value +1 or -1. The direction switches after each pair of loops. Since we know the value of d at all points, we can multiply each side of each inequality by it, adjust the direction of the inequality accordingly and simplify any multiplications of d by a constant to another constant. This leaves us with the following.
Now we note that both x * d and the RHS are integers so we can subtract any real value between 0 and 1 from the RHS without affecting the result of the inequality. We choose to subtract 0.5 from the inequalities of every other pair of while loops in order to establish more of a pattern.
We can now introduce another variable m for the number of steps we take at each pair of while loops.
Finally, we see that the structure of each pair of while loops is identical and can be reduced to a single loop placed inside of another loop. Also, to avoid using real valued numbers I've multiplied the initial value of m; the value m is incremented by; and both sides of each inequality by 2.
This leads to the solution shown at the beginning of this answer.
EDIT: It has been a few years but I had a similar problem and wrote the following solution in F# which I want to share. The word print may have been a misnomer in my original answer but hopefully this non-pseudocode version will address any points raised in the comments regarding versatility and termination conditions. I have added example use cases for spiralling about an arbitrary point and finding the correct solution to the original problem for iterating an NxM matrix.
这是一个 O(1) 解决方案,用于查找平方螺旋中的位置: Fiddle
Here's a O(1) solution to find the position in a squared spiral : Fiddle
我喜欢 python 的生成器。
测试:
您将得到:
I love python's generators.
Testing with:
You get:
这是一个 C++ 解决方案,它表明您可以直接轻松地根据前一个坐标计算下一个 (x, y) 坐标 - 无需跟踪当前方向、半径或其他任何内容:
如果您想要做的只是生成螺旋中的前 N 个点(没有原始问题对 N x M 区域进行屏蔽的约束),代码变得非常简单:
技巧是您可以比较 x 和 y 来确定您位于正方形的哪一侧,这会告诉您要朝哪个方向移动。
Here's a C++ solution that shows that you can calculate the next (x, y) coordinates directly and easily from the previous ones - no need for tracking the current direction, radius, or anything else:
If all you're trying to do is generate the first N points in the spiral (without the original problem's constraint of masking to an N x M region), the code becomes very simple:
The trick is that you can compare x and y to determine what side of the square you're on, and that tells you what direction to move in.
Java 螺旋“高尔夫代码”尝试,基于 C++ 变体。
Java spiral "Code golf" attempt, based on the C++ variant.
TDD,在 Java 中。
SpiralTest.java:
Spiral.java:
TDD, in Java.
SpiralTest.java:
Spiral.java:
哈斯克尔,你选吧:
Haskell, take your pick:
这是我的解决方案(用 Ruby 语言)
Here is my solution (In Ruby)
你的问题看起来像一个叫做螺旋记忆的问题。
在该问题中,网格上的每个方格从位于原点的数字 1 开始以螺旋模式分配。 然后一边螺旋向外一边计数。 例如:
我计算此螺旋图案后每个数字的坐标的解决方案如下:
Your question looks like a question called spiral memory.
In that problem, each square on the grid is allocated in a spiral pattern starting from the number 1 which locates at the origin. And then counting up while spiraling outwards. For example:
My solution for computing the coordinates of each number following this spiral pattern is posted below:
这是在 C 语言中。
我碰巧选择了错误的变量名。 在名称中 T == 顶部,L == 左侧,B == 底部,R == 右侧。 所以,tli 是左上角的 i,brj 是右下角的 j。
This is in C.
I happened to choose bad variable names. In the names T == top, L == left, B == bottom, R == right. So, tli is top left i and brj is bottom right j.
我有一个开源库,pixelscan,它是一个Python库,提供函数以各种空间模式扫描网格上的像素。 包括的空间图案有圆形、环形、网格、蛇形和随机游走。 还有各种变换(例如,剪辑、交换、旋转、平移)。 原始的 OP 问题可以如下解决,
产生点。
库生成器和转换可以链接起来,以各种顺序和空间模式改变点。
I have an open source library, pixelscan, that is a python library that provides functions to scan pixels on a grid in a variety of spatial patterns. Spatial patterns included are circular, rings, grids, snakes, and random walks. There are also various transformations (e.g., clip, swap, rotate, translate). The original OP problem can be solved as follows
which yields the points
The libraries generators and transformations can be chained to change the points in a wide variety of orders and spatial patterns.
下面是针对此问题的 JavaScript (ES6) 迭代解决方案:
以下是如何使用它:
spiralMatrix(0, 0, 1, 100);
这将创建一个向外的螺旋,从坐标 (x = 0) 开始, y = 0),步长为 1,项目总数等于 100。实现始终按以下顺序开始移动 - 上、右、下、左。
请注意,此实现创建方阵。
Here's a JavaScript (ES6) iterative solution to this problem:
Here's how to use it:
spiralMatrix(0, 0, 1, 100);
This will create an outward spiral, starting at coordinates (x = 0, y = 0) with step of 1 and a total number of items equals to 100. The implementation always starts the movement in the following order - up, right, bottom, left.
Please, note that this implementation creates square matrices.
这是 Python 3 中的一个解决方案,用于以螺旋顺时针和逆时针方向打印连续整数。
解释
螺旋由同心正方形组成,例如顺时针旋转的 5x5 正方形如下所示:(
>>>>>
表示“走 5” times right”或增加列索引 5 倍,v
表示向下或增加行索引等。)所有方块的大小都相同,我在同心方块上循环。
对于每个方块,代码有四个循环(每边一个),在每个循环中我们增加或减少列或行索引。
如果
i
是行索引,j
是列索引,则可以通过以下方式构造 5x5 正方形:- 将
j
从 0 增加到 4(5 次)- 将
i
从1增加到4(4次)- 将
j
从 3 递减至 0(4 次)- 将
i
从3递减到1(3次)对于接下来的方块(3x3和1x1),我们做同样的事情,但适当地移动初始和最终索引。
我对每个同心正方形使用了索引
k
,有n//2 + 1个同心正方形。最后,一些关于漂亮打印的数学知识。
打印索引:
Here's a solution in Python 3 for printing consecutive integers in a spiral clockwise and counterclockwise.
Explanation
A spiral is made of concentric squares, for instance a 5x5 square with clockwise rotation looks like this:
(
>>>>>
means "go 5 times right" or increase column index 5 times,v
means down or increase row index, etc.)All squares are the same up to their size, I looped over the concentric squares.
For each square the code has four loops (one for each side), in each loop we increase or decrease the columns or row index.
If
i
is the row index andj
the column index then a 5x5 square can be constructed by:- incrementing
j
from 0 to 4 (5 times)- incrementing
i
from 1 to 4 (4 times)- decrementing
j
from 3 to 0 (4 times)- decrementing
i
from 3 to 1 (3 times)For the next squares (3x3 and 1x1) we do the same but shift the initial and final indices appropriately.
I used an index
k
for each concentric square, there are n//2 + 1 concentric squares.Finally, some math for pretty-printing.
To print the indexes:
这是 c#,linq'ish。
问题的第一个示例 (3x3) 为:
问题的第二个示例 (5x3) 为:
Here's c#, linq'ish.
The question's first example (3x3) would be:
The question's second example (5x3) would be:
这是一个略有不同的版本 - 尝试在 LUA 中使用
递归
和迭代器
。 在每一步中,程序都会在矩阵内进一步下降并循环。 我还为顺时针
或逆时针
螺旋添加了一个额外的标志。 输出从右下角开始并向中心递归循环。This is a slightly different version - trying to use
recursion
anditerators
in LUA. At each step the program descends further inside the matrix and loops. I also added an extra flag to spiralclockwise
oranticlockwise
. The output starts from the bottom right corners and loops recursively towards the center.//PHP实现
//PHP implementation
C# 版本,也可以处理非方形尺寸。
C# version, handles non-square sizes as well.
这是 Julia 的答案:我的方法是在原点
(0,0)
周围分配同心正方形(“螺旋”)中的点,其中每个正方形的边长m = 2n + 1
,生成一个有序字典,以位置编号(从 1 开始为原点)为键,以相应的坐标为值。由于每个螺旋的最大位置位于
(n,-n)
,因此可以通过简单地从该点向后计算来找到其余点,即从右下角开始m- 1
单位,然后重复垂直 3 段m-1
单位。下面以倒序的方式写这个过程,对应的是螺旋如何进行,而不是这个反向计数过程,即
ra
[右升]段递减3(m+1)< /code>,然后
la
[左升序] by2(m+1)
,依此类推 - 希望这是不言自明的。因此,对于第一个示例,将
m = 3
代入方程以查找 n 给出n = (5-1)/2 = 2
和walk(2 )
给出坐标位置的有序字典,您可以通过访问字典的vals
字段将其转换为坐标数组:请注意,对于某些函数 [例如
norm< /code>] 最好将坐标保留在数组中,而不是
Tuple{Int,Int}
,但这里我将它们更改为元组 -(x,y)
——根据要求,使用列表理解。未指定“支持”非方矩阵的上下文(请注意,此解决方案仍然计算离网值),但如果您只想过滤到范围
x
byy
(此处表示x=5
、y=3
)计算完整螺旋后,然后将此矩阵与值相交从步行
。Here's an answer in Julia: my approach is to assign the points in concentric squares ('spirals') around the origin
(0,0)
, where each square has side lengthm = 2n + 1
, to produce an ordered dictionary with location numbers (starting from 1 for the origin) as keys and the corresponding coordinate as value.Since the maximum location per spiral is at
(n,-n)
, the rest of the points can be found by simply working backward from this point, i.e. from the bottom right corner bym-1
units, then repeating for the perpendicular 3 segments ofm-1
units.This process is written in reverse order below, corresponding to how the spiral proceeds rather than this reverse counting process, i.e. the
ra
[right ascending] segment is decremented by3(m+1)
, thenla
[left ascending] by2(m+1)
, and so on - hopefully this is self-explanatory.So for your first example, plugging
m = 3
into the equation to find n givesn = (5-1)/2 = 2
, andwalk(2)
gives an ordered dictionary of locations to coordinates, which you can turn into just an array of coordinates by accessing the dictionary'svals
field:Note that for some functions [e.g.
norm
] it can be preferable to leave the coordinates in arrays rather thanTuple{Int,Int}
, but here I change them into tuples—(x,y)
—as requested, using list comprehension.The context for "supporting" a non-square matrix isn't specified (note that this solution still calculates the off-grid values), but if you want to filter to only the range
x
byy
(here forx=5
,y=3
) after calculating the full spiral thenintersect
this matrix against the values fromwalk
.这是基于您自己的解决方案,但我们可以更聪明地找到角落。 如果 M 和 N 差异很大,这样可以更轻松地了解如何跳过外部区域。
基于生成器的解决方案优于 O(max(n,m)^2),它是 O(nm+abs(nm)^2),因为如果它们不是解决方案的一部分,它会跳过整个条带。
This is based on your own solution, but we can be smarter about finding the corners. This makes it easier to see how you might skip over the areas outside if M and N are very different.
and a generator based solution that is better than O(max(n,m)^2), It is O(nm+abs(n-m)^2) because it skips whole strips if they are not part of the solution.
这是我非常非常糟糕的解决方案,仅使用最基本的 Java 知识。 在这里,我必须将单位放置在螺旋形的区域上。 单位不能放置在其他单位的顶部、山上或海洋中。
要明确一点。 这不是一个好的解决方案。 这是一个非常糟糕的解决方案,是为了让其他人嘲笑它做得有多糟糕而添加的乐趣
感谢任何能够真正阅读此
奖金问题:这个“算法”的运行时间是多少? :P
This is my very very bad solution, made from bare minimum knowledge of Java. Here I have to place units on a field in a spiral. Units cannot be placed on top of other units or on mountains or in the ocean.
To be clear. This is not a good solution. This is a very bad solution added for the fun of other people to laugh at how bad it can be done
Cudos to anyone who can actually read this
Bonus question: What is the running time of this "algorithm"? :P
AutoIt 解决方案
Solution for AutoIt
我最近遇到了类似的挑战,我必须创建一个二维数组并使用螺旋矩阵算法来排序和打印结果。 此 C# 代码适用于 N,N 2D 数组。 为了清晰起见,它很冗长,并且可以进行重构以满足您的需求。
I recently had a similar challenge where I had to create a 2D array and use a spiral matrix algorithm to sort and print the results. This C# code will work with a N,N 2D array. It is verbose for clarity and can likely be re-factored to fit your needs.