Balayage en zig-zag d'un tableau N x N

Question

J'ai un tableau simple. La longueur du tableau a toujours une racine carrée d'un nombre entier. Donc 16, 25, 36 etc.

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

Ce que je fais, c'est arranger le tableau avec le HTML de façon à ce qu'il ressemble à un bloc avec des côtés pairs.

Ce que je veux faire, c'est trier les éléments, de sorte que lorsque je passe le tableau codé JSON à jQuery, il va itérer le tableau, faire un fondu dans le bloc actuel, et ainsi j'obtiendrai une sorte d'animation de vague. J'aimerais donc trier le tableau comme ceci

Ainsi, mon tableau trié ressemblerait à

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

Y a-t-il un moyen de le faire ? Merci

Answer 1

Question très cool. Voici une analyse et un algorithme.

L'un des principaux avantages de cet algorithme est qu'il est entièrement réalisé à l'aide de simples calculs de nombres entiers ; il ne comporte pas d'instructions "if" et donc pas de branchements, ce qui signifie que s'il était compilé, il s'exécuterait très rapidement, même pour de très grandes valeurs de n. Cela signifie également qu'il peut être facilement parallélisé pour diviser le travail entre plusieurs processeurs pour très de grandes valeurs de n.

Considérons une grille de 8x8 (ici, l'entrée est techniquement n = 64, mais pour plus de simplicité dans les formules ci-dessous, j'utiliserai n = 8) suivant ce motif en zigzag, comme suit (avec l'axe des lignes et des colonnes indexé sur 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

Remarquez tout d'abord que la diagonale allant de la partie inférieure gauche (0,7) à la partie supérieure droite (7,0) divise la grille en deux composantes quasi-mirromes :

     [ 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

et

     [ 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

Vous pouvez voir que le bas à droite est juste le haut à gauche reflété et soustrait du carré plus 1 (65 dans ce cas).

Si nous pouvons calculer la partie supérieure gauche, alors la partie inférieure droite peut facilement être calculée en prenant simplement le carré plus 1 ( n * n + 1 ) et en soustrayant la valeur aux coordonnées inverses ( value(n - x - 1, n - y - 1) ).

À titre d'exemple, considérons une paire arbitraire de coordonnées dans la partie inférieure droite, disons (6,3), avec une valeur de 48. En suivant cette formule, cela donnerait (8 * 8 + 1) - value(8 - 6 - 1, 8 - 3 - 1) simplifié à 65 - value(1, 4) . En regardant la partie supérieure gauche, la valeur à (1,4) est 17. Et 65 - 17 == 48 .

Mais nous devons encore calculer la partie supérieure gauche. Notez que celle-ci peut également être subdivisée en deux composantes qui se chevauchent, une composante dont les chiffres augmentent au fur et à mesure que vous vous dirigez vers le haut et la droite :

     [ 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

Et un composant dont les chiffres augmentent au fur et à mesure que l'on descend vers la gauche :

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

Les premiers peuvent également être définis comme les nombres où la somme des coordonnées ( x + y ) est impaire, et les derniers définis comme les nombres où la somme des coordonnées est paire.

Maintenant, l'idée clé ici est que nous dessinons des triangles, donc, sans surprise, le Les nombres triangulaires jouent un rôle de premier plan. La séquence de chiffres du triangle est la suivante : 1, 3, 6, 10, 15, 21, 28, 36, ...

Comme vous pouvez le constater, dans la composante impaire, un nombre triangulaire sur deux commençant par 3 apparaît dans la première ligne (3, 10, 21, 36), et dans la composante paire, un nombre triangulaire sur deux commençant par 1 apparaît dans la première colonne (1, 6, 15, 28).

Plus précisément, pour une paire de coordonnées donnée (x,0) ou (0,y), le numéro du triangle correspondant est triangle(x + 1) ou triangle(y + 1).

Et le reste du graphique peut être calculé en soustrayant progressivement de ces nombres triangulaires vers le haut ou vers le bas des diagonales, ce qui équivaut à soustraire le numéro de ligne ou de colonne donné.

Notez qu'un diagonale peut être défini formellement comme l'ensemble de toutes les cellules ayant une somme donnée de coordonnées. Par exemple, la diagonale avec la somme de coordonnées 3 a pour coordonnées (0,3), (1,2), (2,1) et (3,0). Un seul nombre définit donc chaque diagonale, et ce nombre est également utilisé pour déterminer le nombre de triangles de départ.

Donc, d'après une simple inspection, la formule pour calculer la composante impaire est simplement :

triangle(x + y + 1) - y

Et la formule pour calculer le composant pair est simple :

triangle(x + y + 1) - x

Et la formule bien connue des nombres triangulaires est également simple :

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

Donc, l'algorithme est :

1. Initialise un tableau n x n, où n est la racine carrée de la taille de l'entrée. d'entrée.
2. Calculer les indices pour les coordonnées paires de la partie supérieure gauche. Ceci peut être réalisé en imbriquant deux boucles, une boucle externe externe "y allant de 0 à n - 1" et une boucle interne "x allant de y % 2 à y par pas de 2" (en limitant x à l'actuel y, nous ne regardons que la partie supérieure gauche, comme souhaité, et en commençant à y % 2 et en allant par pas de 2, nous n'obtenons que les coordonnées paires). Les indices de boucle peuvent être insérés dans la formule ci-dessus pour obtenir les résultats. value[x, y] = triangle(x + y + 1) - x .
3. Calculez les indices pour les coordonnées impaires de la partie supérieure gauche. Ceci peut être accompli avec boucles similaires, sauf que la boucle intérieure serait "x allant de y % 2 + 1 à y par pas de 2", pour obtenir uniquement les coordonnées impaires. value[x, y] = triangle(x + y + 1) - y .
4. Calculez les pour la partie en bas à droite par simple soustraction de n * n + 1 comme décrit dans la première partie de ce post. Cela peut être fait avec deux boucles imbriquées qui comptent à rebours (et qui délimitent la boucle intérieure sur la boucle extérieure pour n'obtenir que la partie inférieure droite). value[x, y] = (n * n + 1) - value[n - x - 1, n - y - 1] .
5. Aplatissez la grille dans un tableau (en alignant toutes les lignes) et transformez ensuite l'entrée donnée (de taille n * n) en sortie en utilisant les nombres générés dans la grille comme nouveaux indices.

Answer 2

Voici le mien.

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;

}

Utilisation :

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

Sortie

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 3

Bien qu'il existe déjà de nombreuses solutions à cette question, voici la mienne :

La principale caractéristique qui la différencie des autres solutions :

• Seulement une seule boucle de complexité O(n)
• Seulement les variables temporaires primitives (entières)

La source :

<?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));

À propos, ce type d'algorithme est appelé "balayage en zigzag" et est largement utilisé pour le codage JPEG et MPEG.

Answer 4

Avec une seule boucle et en profitant de la simétrie et sans aucun tri :

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 5

Je l'ai écrit en C# et je ne l'ai pas compilé ou analysé en PHP, mais cette logique devrait fonctionner :

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 version PHP ressemblerait à ceci :

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