php - Zig-zag escanea una matriz N x N

arrays algorithm

Question

Tengo una matriz simple. La longitud de la matriz siempre tiene una raíz cuadrada de un entero. Así que 16, 25, 36 etc.

$array = array(''1'', ''2'', ''3'', ''4'' ... ''25'');

Lo que hago, es arreglar la matriz con HTML para que se vea como un bloque con lados parejos.

Lo que quiero hacer es ordenar los elementos, de modo que cuando pase la matriz codificada JSON a jQuery, iterará la matriz, se desvanecerá en el bloque actual y obtendré una especie de animación de onda. Así que me gustaría ordenar el conjunto de esta manera

Así que mi matriz ordenada sería como

$sorted = array(''1'', ''6'', ''2'', ''3'', ''7'', ''11'', ''16, ''12'' .. ''25'');

¿Hay manera de hacerlo? .. Gracias

Answer 1

Aquí está el mío.

function waveSort(array $array) {
  $dimension = pow(count($array),0.5);
  if((int)$dimension != $dimension) {
    throw new InvalidArgumentException();
  }

  $tempArray = array();
  for($i = 0; $i < $dimension; $i++) {
    $tempArray[] = array_slice($array,$i*$dimension,$dimension);
  }

  $returnArray = array();

  for($i = 0; $i < $dimension * 2 -1; $i++) {
    $diagonal = array();

    foreach($tempArray as $x => $innerArray) {
      if($i - $x >= 0 && $i - $x < $dimension) {
        $diagonal[] = $innerArray[$i - $x];
      }
    }

    if($i % 2 == 1) {
      krsort($diagonal);
    }

    $returnArray = array_merge($returnArray,$diagonal);

  }

  return $returnArray;

}

Uso:

<?php
$a = range(1,25);
var_dump(waveSort($a));

Salida

array(25) {
  [0]=>
  int(1)
  [1]=>
  int(6)
  [2]=>
  int(2)
  [3]=>
  int(3)
  [4]=>
  int(7)
  [5]=>
  int(11)
  [6]=>
  int(16)
  [7]=>
  int(12)
  [8]=>
  int(8)
  [9]=>
  int(4)
  [10]=>
  int(5)
  [11]=>
  int(9)
  [12]=>
  int(13)
  [13]=>
  int(17)
  [14]=>
  int(21)
  [15]=>
  int(22)
  [16]=>
  int(18)
  [17]=>
  int(14)
  [18]=>
  int(10)
  [19]=>
  int(15)
  [20]=>
  int(19)
  [21]=>
  int(23)
  [22]=>
  int(24)
  [23]=>
  int(20)
  [24]=>
  int(25)
}

Answer 2

Aunque ya hay muchas soluciones a esta pregunta, esta es la mía:

La característica principal que lo diferencia de las otras soluciones:

• Sólo un solo bucle de complejidad O (n)
• Solo variables temporales primitivas (enteras)

La fuente:

<?php

function zigzag($input)
{
    $output = array();

    $inc = -1;
    $i = $j = 0;
    $steps = 0;

    $bounds = sqrt(sizeof($input));

    if(fmod($bounds, 1) != 0)
    {
        die(''Matrix must be square'');
    }

    while($steps < sizeof($input))
    {
        if($i >= $bounds) // bottom edge
        {
            $i--;
            $j++;
            $j++;
            $inc = 1;
        }
        if($j >= $bounds) // right edge
        {
            $i++;
            $i++;
            $j--;
            $inc = -1;
        }
        if($j < 0) // left edge
        {
            $j++;
            $inc = 1;
        }
        if($i < 0) // top edge
        {
            $i++;
            $inc = -1;
        }

        $output[] = $input[$bounds * $i + $j];

        $i = $i - $inc;
        $j = $j + $inc;
        $steps++;
    }
    return $output;
}

$a = range(1,25);
var_dump(zigzag($a));

Por cierto, este tipo de algoritmo se denomina "escaneo en zig zag" y se usa en gran medida para la codificación JPEG y MPEG.

Answer 3

Con un solo bucle y aprovechando la simetría y sin ordenaciones:

function waveSort(array $array) {
    $n2=count($array);
    $n=sqrt($n2);
    if((int)$n != $n) throw new InvalidArgumentException();

    $x=0; $y=0; $dir = -1;

    $Result = array_fill(0, $n2, null);
    for ($i=0; $i < $n2/2; $i++) {

        $p=$y * $n +$x;

        $Result[$i]=$array[$p];
        $Result[$n2-1-$i]=$array[$n2-1-$p];

        if (($dir==1)&&($y==0)) {
            $x++;
            $dir *= -1;
        } else if (($dir==-1)&&($x==0)) {
            $y++;
            $dir *= -1;
        } else {
            $x += $dir;
            $y -= $dir;
        }
    }

    return $Result;
}

$a = range(1,25);
var_dump(waveSort($a));

Answer 4

Ejemplo de implementación de Python:

def wave(size):
    curX = 0
    curY = 0
    direction = "down"
    positions = []
    positions.append((curX, curY))
    while not (curX == size-1 and curY == size-1):
        if direction == "down":
            if curY == size-1: #can''t move down any more; move right instead
                curX += 1
            else:
                curY += 1
            positions.append((curX, curY))
            #move diagonally up and right
            while curX < size-1 and curY > 0:
                curX += 1
                curY -= 1
                positions.append((curX, curY))
            direction = "right"
            continue
        else: #direction == "right"
            if curX == size-1: #can''t move right any more; move down instead
                curY += 1
            else:
                curX += 1
            positions.append((curX, curY))
            #move diagonally down and left
            while curY < size-1 and curX > 0:
                curX -= 1
                curY += 1
                positions.append((curX, curY))
            direction = "down"
            continue
    return positions

size = 5
for x, y in wave(size):
    index = 1 + x + (y*size)
    print index, x, y

Salida:

1 0 0
6 0 1
2 1 0
3 2 0
7 1 1
11 0 2
16 0 3
12 1 2
8 2 1
4 3 0
5 4 0
9 3 1
13 2 2
17 1 3
21 0 4
22 1 4
18 2 3
14 3 2
10 4 1
15 4 2
19 3 3
23 2 4
24 3 4
20 4 3
25 4 4

Comedia de una línea de implementación:

def wave(size):
    return [1+x+size*y for x,y in filter(lambda (x,y): x >=0 and x < size and y >= 0 and y < size, reduce(lambda x, y: x+y, [r if i==0 else list(reversed(r)) for i, r in enumerate([(x-delta, delta) for delta in range(size)] for x in range(size*2))], []))]

print wave(5)

salida:

[1, 6, 2, 11, 7, 3, 16, 12, 8, 4, 21, 17, 13, 9, 5, 22, 18, 14, 10, 23, 19, 15, 24, 20, 25]

Answer 5

Esta es mi opinión sobre ella. Es similar a la respuesta de Qiuntus pero más concisa.

function wave($base) {
  $i = 1;
  $a = $base;
  $square = $base*$base;
  $out = array(1);

  while ($i < $square) {
    if ($i > ($square - $base)) { // hit the bottom
      $i++;
      $out[] = $i;
      $a = 1 - $base;
    } elseif ($i % $base == 0) { // hit the right
      $i += $base;
      $out[] = $i;
      $a = $base - 1;
    } elseif (($i - 1) % $base == 0) { // hit the left
      $i += $base;
      $out[] = $i;
      $a = 1 - $base;
    } elseif ($i <= $base) { // hit the top
      $i++;
      $out[] = $i;
      $a = $base - 1;
    }

    if ($i < $square) {
      $i += $a;
      $out[] = $i;
    }
  }

  return $out;
}

Answer 6

Lo escribí en C #, así que no lo compilé / analicé en PHP pero esta lógica debería funcionar:

List<long> newList = new List<long>();
double i = 1;

double root = Math.Sqrt(oldList.Count);
bool direction = true;

while (newList.Count < oldList.Count)
{
    newList.Add(oldList[(int)i - 1]);
    if (direction)
    {
        if (i + root > root * root)
        {
            i++;
            direction = false;
        }
        else if (i % root == 1)
        {
            i += 5;
            direction = false;
        }
        else
        {
            i += root - 1;
        }
    }
    else
    {
        if (i - root <= 0)
        {
            direction = true;
            if (i % root == 0)
            {
                i += root;
            }
            else
            {
                i++;
            }
            direction = true;
        }
        else if (i % root == 0)
        {
            direction = true;
            i += root;
        }
        else
        {
            i += 1 - root;
        }
    }
}

La versión de PHP se vería algo así:

$oldList = ...
$newList = [];
$i = 1;

$root = sqrt(Count($oldList);
$direction = true;

while (count($newList) < count($oldList)
{
    $newList[] = $oldList[$i - 1];
    if ($direction)
    {
        if ($i + $root > $root * $root)
        {
            $i++;
            $direction = false;
        }
        else if ($i % $root == 1)
        {
            $i += 5;
            $direction = false;
        }
        else
        {
            $i += $root - 1;
        }
    }
    else
    {
        if ($i - $root <= 0)
        {
            $direction = true;
            if ($i % $root == 0)
            {
                $i += $root;
            }
            else
            {
                i++;
            }
            direction = true;
        }
        else if ($i % $root == 0)
        {
            $direction = true;
            $i += $root;
        }
        else
        {
            $i += 1 - $root;
        }
    }
}

Answer 7

Muy buena pregunta. Aquí hay un análisis y un algoritmo.

Una ventaja clave para usar este algoritmo es que todo se hace usando cálculos de enteros simples; no tiene declaraciones "si" y, por lo tanto, no tiene ramas, lo que significa que si se compilara, se ejecutaría muy rápidamente incluso con valores muy grandes de n. Esto también significa que puede ser fácilmente paralelo para dividir el trabajo entre varios procesadores para valores muy grandes de n.

Considere una cuadrícula de 8x8 (aquí, la entrada es técnicamente n = 64, pero por simplicidad en las fórmulas a continuación usaré n = 8) siguiendo este patrón de zigzag, así (con el eje de la columna y la columna con indexación 0):

     [ 0] [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7]
[ 0]   1    3    4   10   11   21   22   36
[ 1]   2    5    9   12   20   23   35   37
[ 2]   6    8   13   19   24   34   38   49
[ 3]   7   14   18   25   33   39   48   50
[ 4]  15   17   26   32   40   47   51   58
[ 5]  16   27   31   41   46   52   57   59
[ 6]  28   30   42   45   53   56   60   63
[ 7]  29   43   44   54   55   61   62   64

Primero observe que la diagonal desde la parte inferior izquierda (0,7) a la parte superior derecha (7,0) divide la cuadrícula en dos componentes casi espejados:

     [ 0] [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7]
[ 0]   1    3    4   10   11   21   22   36
[ 1]   2    5    9   12   20   23   35
[ 2]   6    8   13   19   24   34
[ 3]   7   14   18   25   33
[ 4]  15   17   26   32
[ 5]  16   27   31
[ 6]  28  30
[ 7]  29

y

     [ 0] [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7]
[ 0]                                     36
[ 1]                                35   37
[ 2]                           34   38   49
[ 3]                      33   39   48   50
[ 4]                 32   40   47   51   58
[ 5]            31   41   46   52   57   59
[ 6]       30   42   45   53   56   60   63
[ 7]   29  43   44   54   55   61   62   64

Puede ver que la parte inferior derecha es solo la parte superior izquierda reflejada y sustraída del cuadrado más 1 (65 en este caso).

Si podemos calcular la parte superior izquierda, entonces la parte inferior derecha se puede calcular fácilmente simplemente tomando el cuadrado más 1 ( n * n + 1 ) y restando el valor a las coordenadas inversas ( value(n - x - 1, n - y - 1) ).

Como ejemplo, considere un par de coordenadas arbitrarias en la parte inferior derecha, digamos (6,3), con un valor de 48. Siguiendo esta fórmula, se calcularía (8 * 8 + 1) - value(8 - 6 - 1, 8 - 3 - 1) , simplificado a 65 - value(1, 4) . En cuanto a la parte superior izquierda, el valor en (1,4) es 17. Y 65 - 17 == 48 .

Pero todavía tenemos que calcular la parte superior izquierda. Tenga en cuenta que esto también se puede subdividir en dos componentes superpuestos, un componente con los números que aumentan a medida que avanza hacia la derecha:

     [ 0] [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7]
[ 0]        3        10        21        36
[ 1]   2         9        20        35
[ 2]        8        19        34
[ 3]   7        18        33
[ 4]       17        32
[ 5]  16        31
[ 6]       30
[ 7]  29

Y un componente con los números en aumento a medida que se dirige hacia la izquierda:

     [ 0] [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7]
[ 0]   1         4        11        22     
[ 1]        5        12        23     
[ 2]   6        13        24     
[ 3]       14        25     
[ 4]  15        26     
[ 5]       27     
[ 6]  28    
[ 7]    

El primero también se puede definir como los números donde la suma de las coordenadas ( x + y ) es impar, y el último se define como los números donde la suma de las coordenadas es par.

Ahora, la idea clave aquí es que estamos dibujando triángulos aquí, así que, no sorprendentemente, los Números Triangulares desempeñan un papel prominente aquí. La secuencia del número del triángulo es: 1, 3, 6, 10, 15, 21, 28, 36, ...

Como puede ver, en el componente de suma impar, todos los demás números triangulares que comienzan con 3 aparecen en la primera fila (3, 10, 21, 36), y en el componente de suma par, todos los demás números triangulares que comienzan con 1 aparecen en la primera columna (1, 6, 15, 28).

Específicamente, para un par de coordenadas dado (x, 0) o (0, y) el número del triángulo correspondiente es triángulo (x + 1) o triángulo (y + 1).

Y el resto del gráfico se puede calcular restando incrementalmente de estos números triangulares hacia arriba o hacia abajo de las diagonales, lo que equivale a restar el número de fila o columna dado.

Tenga en cuenta que una diagonal se puede definir formalmente como el conjunto de todas las celdas con una suma dada de coordenadas. Por ejemplo, la diagonal con suma de coordenadas 3 tiene coordenadas (0,3), (1,2), (2,1) y (3,0). Entonces, un solo número define cada diagonal, y ese número también se usa para determinar el número triangular inicial.

Entonces, a partir de una simple inspección, la fórmula para calcular el componente de suma impar es simplemente:

triangle(x + y + 1) - y

Y la fórmula para calcular el componente de suma par es simplemente:

triangle(x + y + 1) - x

Y la conocida fórmula para los números de triángulos también es simple:

triangle(n) = (n * (n + 1)) / 2

Entonces, el algoritmo es:

1. Inicialice una matriz nxn, donde n es la raíz cuadrada del tamaño de entrada.
2. Calcule los índices para las coordenadas sumadas de la parte superior izquierda. Esto puede lograrse anidando dos bucles, un bucle externo "y va de 0 a n - 1" y un bucle interno "x va de y% 2 a y en pasos de 2" (al delimitar x en la y actual, solo miramos la parte superior izquierda, según lo deseado, y comenzando en y% 2 y siguiendo los pasos de 2 solo obtenemos las coordenadas de suma par). Los índices de bucle se pueden insertar en la fórmula anterior para obtener los resultados. value[x, y] = triangle(x + y + 1) - x .
3. Calcule los índices para las coordenadas impares de la parte superior izquierda. Esto se puede lograr con bucles similares, excepto que el bucle interno sería "x yendo de y% 2 + 1 a y en pasos de 2", para obtener solo las coordenadas impares. value[x, y] = triangle(x + y + 1) - y .
4. Calcule los índices para la parte inferior derecha mediante una simple resta de n * n + 1 como se describe en la primera parte de esta publicación. Esto se puede hacer con dos bucles anidados contando hacia atrás (y delimitando el interno en el externo para obtener solo la parte inferior derecha). value[x, y] = (n * n + 1) - value[n - x - 1, n - y - 1] .
5. Alise la cuadrícula en una matriz (alineando todas las filas) y luego transforme la entrada dada (de tamaño n * n) en salida utilizando los números generados en la cuadrícula como nuevos índices.

Answer 8

Una solución PHP más, que usa solo for y if , atraviesa la matriz solo una vez

function waveSort(array $array) {

    $elem = sqrt(count($array));

    for($i = 0; $i < $elem; $i++) {
        $multi[] = array_slice($array, $i*$elem , $elem);
    }

    $new = array();
    $rotation = false;
    for($i = 0; $i <= $elem-1; $i++) {
        $k = $i;
        for($j = 0; $j <= $i; $j++) {
            if($rotation)
                $new[] = $multi[$k][$j];
            else
                $new[] = $multi[$j][$k];
            $k--;
        }   
        $rotation = !$rotation;
    }

    for($i = $elem-1; $i > 0; $i--) {
        $k = $elem - $i;

        for($j = $elem-1; $j >= $elem - $i; $j--) {

            if(!$rotation)
                $new[] = $multi[$k][$j];
            else
                $new[] = $multi[$j][$k];
            $k++;
        }   
        $rotation = !$rotation;
    }

    return $new;
}

$array = range(1, 25);
$result = waveSort($array);
print_r($result);

$array = range(1, 36);
$result = waveSort($array);
print_r($result);

Aquí está en acción.