In loop a spirale

Un amico aveva bisogno di un algoritmo che gli permettesse di scorrere gli elementi di una matrice NxM (N e M sono dispari). Ho trovato una soluzione, ma volevo vedere se i miei compagni SO ‘potevano trovare una soluzione migliore.

Sto postando la mia soluzione come risposta a questa domanda.

Esempio di output:

Per una matrice 3×3, l’output dovrebbe essere:

(0, 0) (1, 0) (1, 1) (0, 1) (-1, 1) (-1, 0) (-1, -1) (0, -1) (1, -1 )

Matrice 3x3

Inoltre, l’algoritmo dovrebbe supportare matrici non quadrate, quindi per esempio per una matrice 5×3, l’output dovrebbe essere:

(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)

Matrice 5x3

Ecco la mia soluzione (in Python):

def spiral(X, Y): x = y = 0 dx = 0 dy = -1 for i in range(max(X, Y)**2): if (-X/2 < x <= X/2) and (-Y/2 < y <= Y/2): print (x, y) # DO STUFF... if x == y or (x < 0 and x == -y) or (x > 0 and x == 1-y): dx, dy = -dy, dx x, y = x+dx, y+dy 

C ++ chiunque? Traduzione rapida da python, pubblicata per completezza

 void Spiral( int X, int Y){ int x,y,dx,dy; x = y = dx =0; dy = -1; int t = std::max(X,Y); int maxI = t*t; for(int i =0; i < maxI; i++){ if ((-X/2 <= x) && (x <= X/2) && (-Y/2 <= y) && (y <= Y/2)){ // DO STUFF... } if( (x == y) || ((x < 0) && (x == -y)) || ((x > 0) && (x == 1-y))){ t = dx; dx = -dy; dy = t; } x += dx; y += dy; } } 

Adoro i generatori di Python.

 def spiral(N, M): x,y = 0,0 dx, dy = 0, -1 for dumb in xrange(N*M): if abs(x) == abs(y) and [dx,dy] != [1,0] or x>0 and y == 1-x: dx, dy = -dy, dx # corner, change direction if abs(x)>N/2 or abs(y)>M/2: # non-square dx, dy = -dy, dx # change direction x, y = -y+dx, x+dy # jump yield x, y x, y = x+dx, y+dy 

Test con:

 print 'Spiral 3x3:' for a,b in spiral(3,3): print (a,b), print '\n\nSpiral 5x3:' for a,b in spiral(5,3): print (a,b), 

Ottieni:

 Spiral 3x3: (0, 0) (1, 0) (1, 1) (0, 1) (-1, 1) (-1, 0) (-1, -1) (0, -1) (1, -1) Spiral 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) 

Ecco una soluzione O (1) per trovare la posizione in una spirale quadrata: Fiddle

 function spiral(n) { // given n an index in the squared spiral // p the sum of point in inner square // a the position on the current square // n = p + a var r = Math.floor((Math.sqrt(n + 1) - 1) / 2) + 1; // compute radius : inverse arithmetic sum of 8+16+24+...= var p = (8 * r * (r - 1)) / 2; // compute total point on radius -1 : arithmetic sum of 8+16+24+... var en = r * 2; // points by face var a = (1 + n - p) % (r * 8); // compute de position and shift it so the first is (-r,-r) but (-r+1,-r) // so square can connect var pos = [0, 0, r]; switch (Math.floor(a / (r * 2))) { // find the face : 0 top, 1 right, 2, bottom, 3 left case 0: { pos[0] = a - r; pos[1] = -r; } break; case 1: { pos[0] = r; pos[1] = (a % en) - r; } break; case 2: { pos[0] = r - (a % en); pos[1] = r; } break; case 3: { pos[0] = -r; pos[1] = r - (a % en); } break; } console.log("n : ", n, " r : ", r, " p : ", p, " a : ", a, " --> ", pos); return pos; } 
 let x = 0 let y = 0 let d = 1 let m = 1 while true while 2 * x * d < m print(x, y) x = x + d while 2 * y * d < m print(x, y) y = y + d d = -1 * d m = m + 1 

Ci sono state molte soluzioni proposte per questo problema, scritte in vari linguaggi di programmazione, ma sembrano tutte derivare dallo stesso approccio convoluto. Prenderò in considerazione il problema più generale di calcolare una spirale che può essere espressa concisamente usando l'induzione.

Caso base: Inizia da (0, 0), vai avanti di 1 quadrato, gira a sinistra, vai avanti di 1 quadrato, gira a sinistra. Passo induttivo: andare avanti di n + 1 quadrati, girare a sinistra, andare avanti n + 1 quadrati, girare a sinistra.

L'eleganza matematica nell'esprimere questo problema suggerisce fortemente che ci dovrebbe essere un semplice algoritmo per calcolare la soluzione. Tenendo presente l'astrazione, ho scelto di non implementare l'algoritmo in un linguaggio di programmazione specifico, ma piuttosto come pseudo-codice.

Innanzitutto considererò un algoritmo per calcolare solo 2 iterazioni della spirale usando 4 coppie di cicli while. La struttura di ogni coppia è simile, ma distinta a sé stante. Questo può sembrare strano all'inizio (alcuni loop vengono eseguiti una sola volta) ma passo dopo passo eseguirò le trasformazioni finché non arriveremo a 4 coppie di loop identici e quindi possiamo essere sostituiti con una singola coppia collocata all'interno di un altro ciclo. Questo ci fornirà una soluzione generale di calcolo delle iterazioni senza l'utilizzo di alcun condizionale.

 let x = 0 let y = 0 //RIGHT, UP while x < 1 print(x, y) x = x + 1 while y < 1 print(x, y) y = y + 1 //LEFT, LEFT, DOWN, DOWN while x > -1 print(x, y) x = x - 1 while y > -1 print(x, y) y = y - 1 //RIGHT, RIGHT, RIGHT, UP, UP, UP while x < 2 print(x, y) x = x + 1 while y < 2 print(x, y) y = y + 1 //LEFT, LEFT, LEFT, LEFT, DOWN, DOWN, DOWN, DOWN while x > -2 print(x, y) x = x - 1 while y > -2 print(x, y) y = y - 1 

La prima trasformazione che faremo è l'introduzione di una nuova variabile d, per la direzione, che contiene il valore +1 o -1. La direzione cambia dopo ogni coppia di loop. Poiché conosciamo il valore di d in tutti i punti, possiamo moltiplicare ogni lato di ciascuna disuguaglianza, regolare di conseguenza la direzione della disuguaglianza e semplificare ogni moltiplicazione di d da una costante a un'altra costante. Questo ci lascia con il seguente.

 let x = 0 let y = 0 let d = 1 //RIGHT, UP while x * d < 1 print(x, y) x = x + d while y * d < 1 print(x, y) y = y + d d = -1 * d //LEFT, LEFT, DOWN, DOWN while x * d < 1 print(x, y) x = x + d while y * d < 1 print(x, y) y = y + d d = -1 * d //RIGHT, RIGHT, RIGHT, UP, UP, UP while x * d < 2 print(x, y) x = x + d while y * d < 2 print(x, y) y = y + d d = -1 * d //LEFT, LEFT, LEFT, LEFT, DOWN, DOWN, DOWN, DOWN while x * d < 2 print(x, y) x = x + d while y * d < 2 print(x, y) y = y + d 

Ora notiamo che sia x * d che RHS sono numeri interi in modo da poter sottrarre qualsiasi valore reale tra 0 e 1 dall'RHS senza influenzare il risultato della disuguaglianza. Scegliamo di sottrarre 0,5 dalle disuguaglianze di ogni altra coppia di loop while per stabilire più di un pattern.

 let x = 0 let y = 0 let d = 1 //RIGHT, UP while x * d < 0.5 print(x, y) x = x + d while y * d < 0.5 print(x, y) y = y + d d = -1 * d //LEFT, LEFT, DOWN, DOWN while x * d < 1 print(x, y) x = x + d while y * d < 1 print(x, y) y = y + d d = -1 * d //RIGHT, RIGHT, RIGHT, UP, UP, UP while x * d < 1.5 print(x, y) x = x + d while y * d < 1.5 print(x, y) y = y + d d = -1 * d //LEFT, LEFT, LEFT, LEFT, DOWN, DOWN, DOWN, DOWN while x * d < 2 print(x, y) x = x + d while y * d < 2 print(x, y) y = y + d 

Ora possiamo introdurre un'altra variabile m per il numero di passi che eseguiamo ad ogni coppia di cicli while.

 let x = 0 let y = 0 let d = 1 let m = 0.5 //RIGHT, UP while x * d < m print(x, y) x = x + d while y * d < m print(x, y) y = y + d d = -1 * d m = m + 0.5 //LEFT, LEFT, DOWN, DOWN while x * d < m print(x, y) x = x + d while y * d < m print(x, y) y = y + d d = -1 * d m = m + 0.5 //RIGHT, RIGHT, RIGHT, UP, UP, UP while x * d < m print(x, y) x = x + d while y * d < m print(x, y) y = y + d d = -1 * d m = m + 0.5 //LEFT, LEFT, LEFT, LEFT, DOWN, DOWN, DOWN, DOWN while x * d < m print(x, y) x = x + d while y * d < m print(x, y) y = y + d 

Infine, vediamo che la struttura di ciascuna coppia di loop while è identica e può essere ridotta a un loop singolo posto all'interno di un altro loop. Inoltre, per evitare di usare numeri con valori reali ho moltiplicato il valore iniziale di m; il valore m viene incrementato di; e entrambi i lati di ciascuna disuguaglianza di 2.

Questo porta alla soluzione mostrata all'inizio di questa risposta.

Tentativo “Code golf” a spirale Java, basato sulla variante C ++.

 public static void Spiral(int X, int Y) { int x=0, y=0, dx = 0, dy = -1; int t = Math.max(X,Y); int maxI = t*t; for (int i=0; i < maxI; i++){ if ((-X/2 <= x) && (x <= X/2) && (-Y/2 <= y) && (y <= Y/2)) { System.out.println(x+","+y); //DO STUFF } if( (x == y) || ((x < 0) && (x == -y)) || ((x > 0) && (x == 1-y))) { t=dx; dx=-dy; dy=t; } x+=dx; y+=dy; } } 

Ecco una soluzione in C ++ che mostra che è ansible calcolare le coordinate successive (x, y) direttamente e facilmente da quelle precedenti – non è necessario tenere traccia della direzione, del raggio o di qualsiasi altra cosa:

 void spiral(const int M, const int N) { // Generate an Ulam spiral centered at (0, 0). int x = 0; int y = 0; int end = max(N, M) * max(N, M); for(int i = 0; i < end; ++i) { // Translate coordinates and mask them out. int xp = x + N / 2; int yp = y + M / 2; if(xp >= 0 && xp < N && yp >= 0 && yp < M) cout << xp << '\t' << yp << '\n'; // No need to track (dx, dy) as the other examples do: if(abs(x) <= abs(y) && (x != y || x >= 0)) x += ((y >= 0) ? 1 : -1); else y += ((x >= 0) ? -1 : 1); } } 

Se tutto ciò che stai cercando di fare è generare i primi N punti nella spirale (senza il vincolo del problema originale di mascherare in una regione N x M), il codice diventa molto semplice:

 void spiral(const int N) { int x = 0; int y = 0; for(int i = 0; i < N; ++i) { cout << x << '\t' << y << '\n'; if(abs(x) <= abs(y) && (x != y || x >= 0)) x += ((y >= 0) ? 1 : -1); else y += ((x >= 0) ? -1 : 1); } } 

Il trucco è che puoi confrontare xey per determinare quale lato del quadrato sei su e che ti dice in quale direzione spostarti.

Ecco la mia soluzione (In Ruby)

 def spiral(xDim, yDim) sx = xDim / 2 sy = yDim / 2 cx = cy = 0 direction = distance = 1 yield(cx,cy) while(cx.abs <= sx || cy.abs <= sy) distance.times { cx += direction; yield(cx,cy) if(cx.abs <= sx && cy.abs <= sy); } distance.times { cy += direction; yield(cx,cy) if(cx.abs <= sx && cy.abs <= sy); } distance += 1 direction *= -1 end end spiral(5,3) { |x,y| print "(#{x},#{y})," } 

TDD, in Java.

SpiralTest.java:

 import java.awt.Point; import java.util.List; import junit.framework.TestCase; public class SpiralTest extends TestCase { public void test3x3() throws Exception { assertEquals("(0, 0) (1, 0) (1, 1) (0, 1) (-1, 1) (-1, 0) (-1, -1) (0, -1) (1, -1)", strung(new Spiral(3, 3).spiral())); } public void test5x3() throws Exception { assertEquals("(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)", strung(new Spiral(5, 3).spiral())); } private String strung(List points) { StringBuffer sb = new StringBuffer(); for (Point point : points) sb.append(strung(point)); return sb.toString().trim(); } private String strung(Point point) { return String.format("(%s, %s) ", point.x, point.y); } } 

Spiral.java:

 import java.awt.Point; import java.util.ArrayList; import java.util.List; public class Spiral { private enum Direction { E(1, 0) {Direction next() {return N;}}, N(0, 1) {Direction next() {return W;}}, W(-1, 0) {Direction next() {return S;}}, S(0, -1) {Direction next() {return E;}},; private int dx; private int dy; Point advance(Point point) { return new Point(point.x + dx, point.y + dy); } abstract Direction next(); Direction(int dx, int dy) { this.dx = dx; this.dy = dy; } }; private final static Point ORIGIN = new Point(0, 0); private final int width; private final int height; private Point point; private Direction direction = Direction.E; private List list = new ArrayList(); public Spiral(int width, int height) { this.width = width; this.height = height; } public List spiral() { point = ORIGIN; int steps = 1; while (list.size() < width * height) { advance(steps); advance(steps); steps++; } return list; } private void advance(int n) { for (int i = 0; i < n; ++i) { if (inBounds(point)) list.add(point); point = direction.advance(point); } direction = direction.next(); } private boolean inBounds(Point p) { return between(-width / 2, width / 2, px) && between(-height / 2, height / 2, py); } private static boolean between(int low, int high, int n) { return low <= n && n <= high; } } 

Haskell, fai la tua scelta:

 spiral xy = (0, 0) : concatMap ring [1 .. max x' y'] where ring n | n > x' = left x' n ++ right x' (-n) ring n | n > y' = up ny' ++ down (-n) y' ring n = up nn ++ left nn ++ down nn ++ right nn up xy = [(x, n) | n <- [1-y .. y]]; down = (.) reverse . up right xy = [(n, y) | n <- [1-x .. x]]; left = (.) reverse . right (x', y') = (x `div` 2, y `div` 2) spiral xy = filter (\(x',y') -> 2*abs x' <= x && 2*abs y' <= y) . scanl (\(a,b) (c,d) -> (a+c,b+d)) (0,0) $ concat [ (:) (1,0) . tail $ concatMap (replicate n) [(0,1),(-1,0),(0,-1),(1,0)] | n <- [2,4..max xy] ] 

Questo è in C.

Mi è capitato di scegliere nomi di variabili cattivi. Nei nomi T == top, L == left, B == bottom, R == right. Quindi, tli è in alto a sinistra io e brj è in basso a destra j.

 #include typedef enum { TLTOR = 0, RTTOB, BRTOL, LBTOT } Direction; int main() { int arr[][3] = {{1,2,3},{4,5,6}, {7,8,9}, {10,11,12}}; int tli = 0, tlj = 0, bri = 3, brj = 2; int i; Direction d = TLTOR; while (tli < bri || tlj < brj) { switch (d) { case TLTOR: for (i = tlj; i <= brj; i++) { printf("%d ", arr[tli][i]); } tli ++; d = RTTOB; break; case RTTOB: for (i = tli; i <= bri; i++) { printf("%d ", arr[i][brj]); } brj --; d = BRTOL; break; case BRTOL: for (i = brj; i >= tlj; i--) { printf("%d ", arr[bri][i]); } bri --; d = LBTOT; break; case LBTOT: for (i = bri; i >= tli; i--) { printf("%d ", arr[i][tlj]); } tlj ++; d = TLTOR; break; } } if (tli == bri == tlj == brj) { printf("%d\n", arr[tli][tlj]); } } 

Ecco c #, linq’ish.

 public static class SpiralCoords { public static IEnumerable> GenerateOutTo(int radius) { //TODO trap negative radius. 0 is ok. foreach(int r in Enumerable.Range(0, radius + 1)) { foreach(Tuple coord in GenerateRing(r)) { yield return coord; } } } public static IEnumerable> GenerateRing(int radius) { //TODO trap negative radius. 0 is ok. Tuple currentPoint = Tuple.Create(radius, 0); yield return Tuple.Create(currentPoint.Item1, currentPoint.Item2); //move up while we can while (currentPoint.Item2 < radius) { currentPoint.Item2 += 1; yield return Tuple.Create(currentPoint.Item1, currentPoint.Item2); } //move left while we can while (-radius < currentPoint.Item1) { currentPoint.Item1 -=1; yield return Tuple.Create(currentPoint.Item1, currentPoint.Item2); } //move down while we can while (-radius < currentPoint.Item2) { currentPoint.Item2 -= 1; yield return Tuple.Create(currentPoint.Item1, currentPoint.Item2); } //move right while we can while (currentPoint.Item1 < radius) { currentPoint.Item1 +=1; yield return Tuple.Create(currentPoint.Item1, currentPoint.Item2); } //move up while we can while (currentPoint.Item2 < -1) { currentPoint.Item2 += 1; yield return Tuple.Create(currentPoint.Item1, currentPoint.Item2); } } } 

Il primo esempio della domanda (3x3) sarebbe:

 var coords = SpiralCoords.GenerateOutTo(1); 

Il secondo esempio della domanda (5x3) sarebbe:

 var coords = SpiralCoords.GenerateOutTo(2).Where(x => abs(x.Item2) < 2); 

Questa è la mia pessima soluzione, basata sulla minima conoscenza di Java. Qui devo posizionare unità su un campo in una spirale. Le unità non possono essere posizionate sopra altre unità o sulle montagne o nell’oceano.

Per essere chiari. Questa non è una buona soluzione. Questa è una pessima soluzione aggiunta per il divertimento di altre persone a ridere di quanto male possa essere fatto

 private void unitPlacementAlgorithm(Position p, Unit u){ int i = p.getRow(); int j = p.getColumn(); int iCounter = 1; int jCounter = 0; if (getUnitAt(p) == null) { unitMap.put(p, u); } else { iWhileLoop(i, j, iCounter, jCounter, -1, u); } } private void iWhileLoop(int i, int j, int iCounter, int jCounter, int fortegn, Unit u){ if(iCounter == 3) { for(int k = 0; k < 3; k++) { if(k == 2) { //This was added to make the looping stop after 9 units System.out.println("There is no more room around the city"); return; } i--; if (getUnitAt(new Position(i, j)) == null && !(getTileAt(new Position(i, j)).getTypeString().equals(GameConstants.OCEANS)) && !(getTileAt(new Position(i, j)).getTypeString().equals(GameConstants.MOUNTAINS))) { unitMap.put(new Position(i, j), u); return; } iCounter--; } } while (iCounter > 0) { if (fortegn > 0) { i++; } else { i--; } if (getUnitAt(new Position(i, j)) == null && !(getTileAt(new Position(i, j)).getTypeString().equals(GameConstants.OCEANS)) && !(getTileAt(new Position(i, j)).getTypeString().equals(GameConstants.MOUNTAINS))) { unitMap.put(new Position(i, j), u); return; } iCounter--; jCounter++; } fortegn *= -1; jWhileLoop(i, j, iCounter, jCounter, fortegn, u); } private void jWhileLoop(int i, int j, int iCounter, int jCounter, int fortegn, Unit u) { while (jCounter > 0) { if (fortegn > 0) { j++; } else { j--; } if (getUnitAt(new Position(i, j)) == null && !(getTileAt(new Position(i, j)).getTypeString().equals(GameConstants.OCEANS)) && !(getTileAt(new Position(i, j)).getTypeString().equals(GameConstants.MOUNTAINS))) { unitMap.put(new Position(i, j), u); return; } jCounter--; iCounter++; if (jCounter == 0) { iCounter++; } } iWhileLoop(i, j, iCounter, jCounter, fortegn, u); } 

Cudos a chiunque possa leggerlo

Domanda bonus: qual è il tempo di esecuzione di questo “algoritmo”? : P

Questa è una versione leggermente diversa: provare a utilizzare recursion e iterators in LUA. Ad ogni passo il programma scende ulteriormente all’interno della matrice e dei loop. Ho anche aggiunto una bandiera in più a spirale in clockwise o anticlockwise . L’uscita inizia dagli angoli in basso a destra e i loop ricorsivamente verso il centro.

 local row, col, clockwise local SpiralGen SpiralGen = function(loop) -- Generator of elements in one loop local startpos = { x = col - loop, y = row - loop } local IteratePosImpl = function() -- This function calculates returns the cur, next position in a loop. If called without check, it loops infinitely local nextpos = {x = startpos.x, y = startpos.y} local step = clockwise and {x = 0, y = -1} or { x = -1, y = 0 } return function() curpos = {x = nextpos.x, y = nextpos.y} nextpos.x = nextpos.x + step.x nextpos.y = nextpos.y + step.y if (((nextpos.x == loop or nextpos.x == col - loop + 1) and step.y == 0) or ((nextpos.y == loop or nextpos.y == row - loop + 1) and step.x == 0)) then --Hit a corner in the loop local tempstep = {x = step.x, y = step.y} step.x = clockwise and tempstep.y or -tempstep.y step.y = clockwise and -tempstep.x or tempstep.x -- retract next step with new step nextpos.x = curpos.x + step.x nextpos.y = curpos.y + step.y end return curpos, nextpos end end local IteratePos = IteratePosImpl() -- make an instance local curpos, nextpos = IteratePos() while (true) do if(nextpos.x == startpos.x and nextpos.y == startpos.y) then coroutine.yield(curpos) SpiralGen(loop+1) -- Go one step inner, since we're done with this loop break -- done with inner loop, get out else if(curpos.x < loop + 1 or curpos.x > col - loop or curpos.y < loop + 1 or curpos.y > row - loop) then break -- done with all elemnts, no place to loop further, break out of recursion else local curposL = {x = curpos.x, y = curpos.y} curpos, nextpos = IteratePos() coroutine.yield(curposL) end end end end local Spiral = function(rowP, colP, clockwiseP) row = rowP col = colP clockwise = clockwiseP return coroutine.wrap(function() SpiralGen(0) end) -- make a coroutine that returns all the values as an iterator end --test for pos in Spiral(10,2,true) do print (pos.y, pos.x) end for pos in Spiral(10,9,false) do print (pos.y, pos.x) end 

Python esegue il looping della spirale in senso orario usando la risposta Can Berk Güder .

 def spiral(X, Y): x = y = 0 dx = 0 dy = 1 for i in range(max(X, Y)**2): if (-X/2 < x <= X/2) and (-Y/2 < y <= Y/2): print (x, y) # DO STUFF... if x == -y or (x < 0 and x == y) or (x > 0 and x-1 == y): dx, dy = dy, -dx x, y = x+dx, y+dy 

Questo si basa sulla tua soluzione, ma possiamo essere più intelligenti nel trovare gli angoli. Questo rende più facile vedere come si può saltare le aree esterne se M e N sono molto diverse.

 def spiral(X, Y): x = y = 0 dx = 0 dy = -1 s=0 ds=2 for i in range(max(X, Y)**2): if abs(x) <= X and abs(y) <= Y/2: print (x, y) # DO STUFF... if i==s: dx, dy = -dy, dx s, ds = s+ds/2, ds+1 x, y = x+dx, y+dy 

e una soluzione basata su generatore che è migliore di O (max (n, m) ^ 2), è O (nm + abs (nm) ^ 2) perché salta intere strisce se non fanno parte della soluzione.

 def spiral(X,Y): X = X+1>>1 Y = Y+1>>1 x = y = 0 d = side = 1 while x 
 Here is my attempt for simple C solution. First print the outer spiral and move one block inside..and repeat. #define ROWS 5 #define COLS 5 //int A[ROWS][COLS] = { {1, 2, 3, 4}, {5, 6, 7, 8}, {11, 12, 13, 14}, {15, 16, 17, 18} }; //int A[ROWS][COLS] = { {1, 2, 3}, {6, 7, 8}, { 12, 13, 14} }; //int A[ROWS][COLS] = { {1, 2}, {3, 4}}; int A[ROWS][COLS] = { {1, 2, 3, 4, 5}, {6, 7, 8, 9, 10}, {11, 12, 13, 14, 15} , {16, 17, 18, 19, 20}, {21, 22, 23, 24, 25} }; void print_spiral(int rows, int cols) { int row = 0; int offset = 0; while (offset < (ROWS - 1)) { /* print one outer loop at a time. */ for (int col = offset; col <= cols; col++) { printf("%d ", A[offset][col]); } for (row = offset + 1; row <= rows; row++) { printf("%d ", A[row][cols]); } for (int col = cols - 1; col >= offset; col--) { printf("%d ", A[rows][col]); } for (row = rows - 1; row >= offset + 1; row--) { printf("%d ", A[row][offset]); } /* Move one block inside */ offset++; rows--; cols--; } printf("\n"); } int _tmain(int argc, _TCHAR* argv[]) { print_spiral(ROWS-1, COLS-1); return 0; } 

Soluzione per AutoIt

 #include  #include  Func SpiralSearch($xMax,$yMax) $x = 0 $y = 0 $dx = 0 $dy = -1 for $i=0 To _max($xMax, $yMax)^2-1 Step 1 if -$xMax/2 < $x and $x <= $xMax/2 And -$yMax/2 < $y And $y <= $yMax/2 Then MsgBox(0, "We are here ", $x & " " & $y) EndIf if $x == $y or ($x < 0 and $x == -$y) or ($x > 0 and $x == 1-$y) Then _ArraySwap ($dx, $dy) $dx=-$dx EndIf $x += $dx $y += $dy Next EndFunc 

Recentemente ho avuto una sfida simile in cui ho dovuto creare un array 2D e utilizzare un algoritmo a matrice spirale per ordinare e stampare i risultati. Questo codice C # funzionerà con un array N, N 2D. È prolisso per chiarezza e può probabilmente essere rielaborato in base alle proprie esigenze.

 //CREATE A NEW MATRIX OF SIZE 4 ROWS BY 4 COLUMNS - SCALE MATRIX SIZE HERE SpiralMatrix SM = new SpiralMatrix(4, 4); string myData = SM.Read(); public class SpiralMatrix { //LETS BUILD A NEW MATRIX EVERY TIME WE INSTANTIATE OUR CLASS public SpiralMatrix(int Rows, int Cols) { Matrix = new String[Rows, Cols]; int pos = 1; for(int r = 0; r= 0 && Col < Matrix.GetLength(1) && Col >= 0) { //CHECK COORDINATE VALUE if (Matrix[Row, Col] != ConsumeChar) return true; else return false; } else { //WE ARE OUT OF BOUNDS return false; } } public string ConsumePos(int Row, int Col) { string n = Matrix[Row, Col]; Matrix[Row, Col] = ConsumeChar; return n; } public string ConsumeChar = "X"; public string[,] Matrix; } 

// implementazione PHP

 function spiral($n) { $r = intval((sqrt($n + 1) - 1) / 2) + 1; // compute radius : inverse arithmetic sum of 8+16+24+...= $p = (8 * $r * ($r - 1)) / 2; // compute total point on radius -1 : arithmetic sum of 8+16+24+... $en = $r * 2; // points by face $a = (1 + $n - $p) % ($r * 8); // compute de position and shift it so the first is (-r,-r) but (-r+1,-r) // so square can connect $pos = array(0, 0, $r); switch (intval($a / ($r * 2))) { // find the face : 0 top, 1 right, 2, bottom, 3 left case 0: $pos[0] = $a - $r; $pos[1] = -$r; break; case 1: $pos[0] = $r; $pos[1] = ($a % $en) - $r; break; case 2: $pos[0] = $r - ($a % $en); $pos[1] = $r; break; case 3: $pos[0] = -$r; $pos[1] = $r - ($a % $en); break; } return $pos; } for ($i = 0; $i < 168; $i++) { echo '
'; print_r(spiral($i)); echo '

'; }

Ne ho fatto uno con un amico che regola la spirale per le proporzioni della canvas su Javascript. La migliore soluzione che ho ottenuto per l’evoluzione dell’immagine pixel per pixel, riempiendo l’intera immagine.

Spero che ne aiuti qualcuno.

 var width = 150; var height = 50; var x = -(width - height)/2; var y = 0; var dx = 1; var dy = 0; var x_limit = (width - height)/2; var y_limit = 0; var counter = 0; var canvas = document.getElementById("canvas"); var ctx = canvas.getContext('2d'); setInterval(function(){ if ((-width/2 < x && x <= width/2) && (-height/2 < y && y <= height/2)) { console.log("[ " + x + " , " + y + " ]"); ctx.fillStyle = "#FF0000"; ctx.fillRect(width/2 + x, height/2 - y,1,1); } if( dx > 0 ){//Dir right if(x > x_limit){ dx = 0; dy = 1; } } else if( dy > 0 ){ //Dir up if(y > y_limit){ dx = -1; dy = 0; } } else if(dx < 0){ //Dir left if(x < (-1 * x_limit)){ dx = 0; dy = -1; } } else if(dy < 0) { //Dir down if(y < (-1 * y_limit)){ dx = 1; dy = 0; x_limit += 1; y_limit += 1; } } counter += 1; //alert (counter); x += dx; y += dy; }, 1); 

Puoi vederlo lavorando su http://jsfiddle.net/hitbyatruck/c4Kd6/ . Assicurati solo di modificare la larghezza e l'altezza della canvas su javascript vars e sugli attributi sull'HTML.

Ho una libreria open source, pixelscan , che è una libreria python che fornisce funzioni per scansionare i pixel su una griglia in una varietà di pattern spaziali. I modelli spaziali inclusi sono circolari, anelli, griglie, serpenti e passeggiate casuali. Ci sono anche varie trasformazioni (ad esempio, clip, scambio, rotazione, traduzione). Il problema dell’OP originale può essere risolto come segue

 for x, y in clip(swap(ringscan(0, 0, 0, 2)), miny=-1, maxy=1): print x, y 

che produce i punti

 (0,0) (1,0) (1,1) (0,1) (-1,1) (-1,0) (-1,-1) (0,-1) (1,-1) (2,0) (2,1) (-2,1) (-2,0) (-2,-1) (2,-1) 

Le librerie di generatori e trasformazioni possono essere concatenati per cambiare i punti in un’ampia varietà di ordini e modelli spaziali.

Solo per divertimento in Javascript:

 function spiral(x, y) { var iy = ix = 0 , hr = (x - 1) / 2 , vr = (y - 1) / 2 , tt = x * y , matrix = [] , step = 1 , dx = 1 , dy = 0; while(matrix.length < tt) { if((ix <= hr && ix >= (hr * -1)) && (iy <= vr && (iy >= (vr * -1)))) { console.log(ix, iy); matrix.push([ix, iy]); } ix += dx; iy += dy; // check direction if(dx !== 0) { // increase step if(ix === step && iy === (step * -1)) step++; // horizontal range reached if(ix === step || (ix === step * -1)) { dy = (ix === iy)? (dx * -1) : dx; dx = 0; } } else { // vertical range reached if(iy === step || (iy === step * -1)) { dx = (ix === iy)? (dy * -1) : dy; dy = 0; } } } return matrix; } var sp = spiral(5, 3); 

C# version, handles non-square sizes as well.

 private static Point[] TraverseSpiral(int width, int height) { int numElements = width * height + 1; Point[] points = new Point[numElements]; int x = 0; int y = 0; int dx = 1; int dy = 0; int xLimit = width - 0; int yLimit = height - 1; int counter = 0; int currentLength = 1; while (counter < numElements) { points[counter] = new Point(x, y); x += dx; y += dy; currentLength++; if (dx > 0) { if (currentLength >= xLimit) { dx = 0; dy = 1; xLimit--; currentLength = 0; } } else if (dy > 0) { if (currentLength >= yLimit) { dx = -1; dy = 0; yLimit--; currentLength = 0; } } else if (dx < 0) { if (currentLength >= xLimit) { dx = 0; dy = -1; xLimit--; currentLength = 0; } } else if (dy < 0) { if (currentLength >= yLimit) { dx = 1; dy = 0; yLimit--; currentLength = 0; } } counter++; } Array.Reverse(points); return points; } 

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).

  rec BuildSpiralIndex(long w, long h, long index = -1) { long count = 0 , x = -1, y = -1, dir = 1, phase=0, pos = 0, length = 0, totallength = 0; bool isVertical = false; if(index>=(w*h)) return null; do { isVertical = (count % 2) != 0; length = (isVertical ? h : w) - count/2 - count%2 ; totallength += length; count++; } while(totallength 1 ? phase : w - phase); y = ((pos == 1 || pos == 2) ? h - phase : phase) + (1 * (pos == 3 ? 1 : 0)); dir = pos > 1 ? -1 : 1; if (isVertical) y -= (totallength - index - 1) * dir; else x -= (totallength - index -1) * dir; return new rec { X = x, Y = y }; } 

Here’s a JavaScript (ES6) iterative solution to this problem:

 let spiralMatrix = (x, y, step, count) => { let distance = 0; let range = 1; let direction = 'up'; for ( let i = 0; i < count; i++ ) { console.log('x: '+x+', y: '+y); distance++; switch ( direction ) { case 'up': y += step; if ( distance >= range ) { direction = 'right'; distance = 0; } break; case 'right': x += step; if ( distance >= range ) { direction = 'bottom'; distance = 0; range += 1; } break; case 'bottom': y -= step; if ( distance >= range ) { direction = 'left'; distance = 0; } break; case 'left': x -= step; if ( distance >= range ) { direction = 'up'; distance = 0; range += 1; } break; default: break; } } } 

Ecco come usarlo:

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.

Davidont’s excellent solution in VB.Net

  Public Function Spiral(n As Integer) As RowCol ' given n an index in the squared spiral ' p the sum of point in inner square ' a the position on the current square ' n = p + a ' starts with row 0 col -1 Dim r As Integer = CInt(Math.Floor((Math.Sqrt(n + 1) - 1) / 2) + 1) ' compute radius : inverse arithmetic sum of 8+16+24+...= Dim p As Integer = (8 * r * (r - 1)) \ 2 ' compute total point on radius -1 : arithmetic sum of 8+16+24+... Dim en As Integer = r * 2 ' points by face Dim a As Integer = (1 + n - p) Mod (r * 8) ' compute the position and shift it so the first is (-r,-r) but (-r+1,-r) ' so square can connect Dim row As Integer Dim col As Integer Select Case Math.Floor(a \ (r * 2)) ' find the face : 0 top, 1 right, 2, bottom, 3 left Case 0 row = a - r col = -r Case 1 row = r col = (a Mod en) - r Case 2 row = r - (a Mod en) col = r Case 3 row = -r col = r - (a Mod en) End Select Return New RowCol(row, col) End Function 

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 length m = 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, ie from the bottom right corner by m-1 units, then repeating for the perpendicular 3 segments of m-1 units.

This process is written in reverse order below, corresponding to how the spiral proceeds rather than this reverse counting process, ie the ra [right ascending] segment is decremented by 3(m+1) , then la [left ascending] by 2(m+1) , and so on – hopefully this is self-explanatory.

 import DataStructures: OrderedDict, merge function spiral(loc::Int) s = sqrt(loc-1) |> floor |> Int if s % 2 == 0 s -= 1 end s = (s+1)/2 |> Int return s end function perimeter(n::Int) n > 0 || return OrderedDict([1,[0,0]]) m = 2n + 1 # width/height of the spiral [square] indexed by n # loc_max = m^2 # loc_min = (2n-1)^2 + 1 ra = [[m^2-(y+3m-3), [n,ny]] for y in (m-2):-1:0] la = [[m^2-(y+2m-2), [yn,n]] for y in (m-2):-1:0] ld = [[m^2-(y+m-1), [-n,yn]] for y in (m-2):-1:0] rd = [[m^2-y, [ny,-n]] for y in (m-2):-1:0] return OrderedDict(vcat(ra,la,ld,rd)) end function walk(n) cds = OrderedDict(1 => [0,0]) n > 0 || return cds for i in 1:n cds = merge(cds, perimeter(i)) end return cds end 

So for your first example, plugging m = 3 into the equation to find n gives n = (5-1)/2 = 2 , and walk(2) gives an ordered dictionary of locations to coordinates, which you can turn into just an array of coordinates by accessing the dictionary’s vals field:

 walk(2) DataStructures.OrderedDict{Any,Any} with 25 entries: 1 => [0,0] 2 => [1,0] 3 => [1,1] 4 => [0,1] ⋮ => ⋮ [(co[1],co[2]) for co in walk(2).vals] 25-element Array{Tuple{Int64,Int64},1}: (0,0) (1,0) ⋮ (1,-2) (2,-2) 

Note that for some functions [eg norm ] it can be preferable to leave the coordinates in arrays rather than Tuple{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 by y (here for x=5 , y=3 ) after calculating the full spiral then intersect this matrix against the values from walk .

 grid = [[x,y] for x in -2:2, y in -1:1] 5×3 Array{Array{Int64,1},2}: [-2,-1] [-2,0] [-2,1] ⋮ ⋮ ⋮ [2,-1] [2,0] [2,1] [(co[1],co[2]) for co in intersect(walk(2).vals, grid)] 15-element Array{Tuple{Int64,Int64},1}: (0,0) (1,0) ⋮ (-2,0) (-2,-1) 

This is my approach for a square spiral in c#, i made this some time ago, i just thought i could add it, since it’s different from all the others, not the best, but just a different way, i am sure it can be adapted for a non-square too.

This approach i take the max number of steps in, instead of the max vector tho.

The main thing about this approach is the corners, there’s some adjustments for the first step and the “progress” step needed to go out of the “corner” in the right bottom corner.

 private void Spiral(int sequence) { const int x = 0; const int y = 1; int[,] matrix = new int[2, sequence]; int dirX, dirY, prevX, prevY, curr; dirX = dirY = prevX = prevY = curr = default(int); do { if (curr > 0) { prevX = matrix[x, curr - 1]; prevY = matrix[y, curr - 1]; } //Change direction based on the corner. if (Math.Abs(prevX) == Math.Abs(prevY) && curr > 0) { dirX = dirY = 0; if (prevY > 0 && prevX > 0) dirX = -1; else if (prevY > 0 && prevX < 0) dirY = -1; else if (prevY < 0 && prevX < 0) dirX = 1; else if (prevY < 0 && prevX > 0) //Move forward dirX = 1; else if (prevY == 0 && prevX == 0) //For the first step. dirX = 1; } else if (prevY < 0 && prevX > 0 && (Math.Abs(matrix[x, curr - 2]) == Math.Abs(matrix[y, curr - 2]))) //Move forward { dirX = 0; dirY = 1; } else if (prevX == 1 && prevY == 0) //For the second step. { dirY = 1; dirX = 0; } matrix[x, curr] = prevX + dirX; matrix[y, curr] = prevY + dirY; System.Console.Write($"({matrix[x, curr]},{matrix[y, curr]}) "); } while (++curr < sequence); } 

Here’s a solution in Python 3 for printing consecutive integers in a spiral clockwise and counterclockwise.

 import math def sp(n): # spiral clockwise a=[[0 for x in range(n)] for y in range(n)] last=1 for k in range(n//2+1): for j in range(k,nk): a[k][j]=last last+=1 for i in range(k+1,nk): a[i][j]=last last+=1 for j in range(nk-2,k-1,-1): a[i][j]=last last+=1 for i in range(nk-2,k,-1): a[i][j]=last last+=1 s=int(math.log(n*n,10))+2 # compute size of cell for printing form="{:"+str(s)+"}" for i in range(n): for j in range(n): print(form.format(a[i][j]),end="") print("") sp(3) # 1 2 3 # 8 9 4 # 7 6 5 sp(4) # 1 2 3 4 # 12 13 14 5 # 11 16 15 6 # 10 9 8 7 def sp_cc(n): # counterclockwise a=[[0 for x in range(n)] for y in range(n)] last=1 for k in range(n//2+1): for j in range(nk-1,k-1,-1): a[nk-1][j]=last last+=1 for i in range(nk-2,k-1,-1): a[i][j]=last last+=1 for j in range(k+1,nk): a[i][j]=last last+=1 for i in range(k+1,nk-1): a[i][j]=last last+=1 s=int(math.log(n*n,10))+2 # compute size of cell for printing form="{:"+str(s)+"}" for i in range(n): for j in range(n): print(form.format(a[i][j]),end="") print("") sp_cc(5) # 9 10 11 12 13 # 8 21 22 23 14 # 7 20 25 24 15 # 6 19 18 17 16 # 5 4 3 2 1 

Spiegazione

A spiral is made of concentric squares, for instance a 5×5 square with clockwise rotation looks like this:

  5x5 3x3 1x1 >>>>> ^ v >>> ^ v + ^ v + > ^ v <<< <<< 

( >>>>> 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 and j 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:

 def spi_cc(n): # counter-clockwise a=[[0 for x in range(n)] for y in range(n)] ind=[] last=n*n for k in range(n//2+1): for j in range(nk-1,k-1,-1): ind.append((nk-1,j)) for i in range(nk-2,k-1,-1): ind.append((i,j)) for j in range(k+1,nk): ind.append((i,j)) for i in range(k+1,nk-1): ind.append((i,j)) print(ind) spi_cc(5)