Matriz y algoritmo "espiral"

Question

quería preguntar si había algo de algoritmo listo, eso me permitió hacer esto: tengo una matriz m (col) x n (fila) con m x n elementos. Quiero dar posición a este elemento a partir del centro y que gira como una espiral, por ejemplo, para un 3x3 matriz tengo 9 elementos así definidos:

5 6 7 
4 9 8 
3 2 1 

o para matriz Una 4 x 3 tengo 12 elementos, hacer definido:

8 9 10 1 
    7 12 11 2 
    6 5 4 3 

o de nuevo, un 5x2 matriz tengo 10 elementos así definidos:

3 4 
    7 8 
    10 9 
    6 5 
    2 1 

etc. he resuelto básicamente la definición de un conjunto de número entero de elemen mxn ts y cargar manualmente el valor, pero en generel para mí como esa matriz hecha de algoritmo de forma automática. Gracias a quien me puede ayudar a encontrar algo así, muchas gracias.

ACTUALIZACIÓN

Este código, hago exactely acerca quiero tener, pero no está en Delphi; solo necesito que empiece desde 1 y no desde 0. Lo importante para mí es que es válido para cualquier matriz m x n. ¿Quién me ayudó a traducirlo en 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)) 

Gracias otra vez mucho.

Answer 1

Basado en el clásico spiral algorithm. matriz de soporte no cuadrados:

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

Aquí está la implementación de JavaScript comentada para lo que está tratando de lograr.

// 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; 
} 
} 

El código no es el más eficiente, ya que se acerca la espiral ingenuamente y sin comprobar previamente si la ubicación es caminar en es válido. Solo verifica la validez de la ubicación actual justo antes de intentar establecer el valor en ella.

Answer 3

¡Ahí lo tienes! Después de 30 errores de sintaxis en algunos ...

En ideone.com, lo ejecuté con algunas pruebas y parece funcionar bien. Creo que todavía se puede ver la salida y ejecutarla usted mismo ...

Puse algunos comentarios en el código. Lo suficiente como para entender la mayor parte. El sistema de navegación principal es un poco más difícil de explicar. En resumen, hacer una espiral va en la primera dirección 1 vez, la segunda 1 vez, la tercera 2 veces, la cuarta 2 veces, la quinta 3 veces, 3, 4, 4, 5, 5, y así sucesivamente. Uso lo que llamé seed y step para obtener este comportamiento.

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. 

Si realmente necesita eso para imprimir espirales de texto, le dejaré alinear los números. Solo acomódelos con espacios.

EDIT:

olvidaba ... Con el fin de hacer que funcione en Ideone, puse los parámetros en 2 líneas como entrada. m, luego n.

Por ejemplo:

5 
2 

produce

3 4 
7 8 
10 9 
6 5 
2 1 

Answer 4

Aunque la pregunta ya está respondida, esta es una solución alternativa (posiblemente más simple). La solución está en python (usando numpy para matrices bidimendionales), pero se puede portar fácilmente.

La idea básica es usar el hecho de que el número de pasos es conocido (m * n) como condición final, y para calcular correctamente el siguiente elemento del bucle en cada iteració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 

Y aquí algunas salidas:

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