Zig-zag扫描N×N阵列

Question

我有一个简单的数组.数组长度始终具有整数的平方根.所以16,25,36等

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

我所做的是使用HTML排列数组,使其看起来像一个具有均匀边的块.

我想要做的是对元素进行排序,这样当我将JSON编码的数组传递给jQuery时,它将迭代数组,淡入当前块,因此我会得到一种波形动画.所以我想对数组进行排序

所以我的排序数组看起来像

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

有办法吗？谢谢

Answer 1

很酷的问题.这是一个分析和算法.

使用这种算法的一个关键优势是它都是使用简单的整数计算完成的; 它没有"if"语句,因此没有分支,这意味着如果它被编译,即使对于非常大的n值,它也会非常快速地执行.这也意味着它可以很容易地并行化,以便在多个处理器之间划分非常大的n值.

考虑一个8x8网格(这里,输入在技术上是n = 64,但为了简化下面的公式,我将使用n = 8)遵循这个Z字形模式,就像这样(使用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

首先注意从左下角(0,7)到右上角(7,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
[ 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

和

     [ 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

您可以看到右下角只是左上角的镜像,并从正方形加1(本例中为65)中减去.

如果我们可以计算左上部分,那么只需取正方形加1(n * n + 1)并减去反坐标(value(n - x - 1, n - y - 1))处的值就可以很容易地计算出右下部分.

作为一个例子,考虑右下角部分的一对任意坐标,比如说(6,3),值为48.遵循这个公式可以解决(8 * 8 + 1) - value(8 - 6 - 1, 8 - 3 - 1),简化为65 - value(1, 4).看左上角,(1,4)的值是17 65 - 17 == 48.

但我们仍然需要计算左上角部分.请注意,这也可以进一步细分为两个重叠的组件,一个组件的数字随着您向右上方的增加而增加:

     [ 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

当你向左下方时,一个组件的数字会增加:

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

前者也可以定义为坐标(x + y)之和为奇数的数字,后者定义为坐标之和为偶数的数字.

现在,这里的关键见解是我们在这里绘制三角形,所以,三角数在这里起着重要的作用,并不令人惊讶.三角形数字序列为:1,3,6,10,15,21,28,36 ......

如您所见,在奇和组件中,每个其他以3开头的三角形数字出现在第一行(3,10,21,36)中,而在偶数组件中,每个其他以1开头的三角形数字出现在第一列(1,6,15,28).

具体地,对于给定的坐标对(x,0)或(0,y),对应的三角形数是三角形(x + 1)或三角形(y + 1).

并且可以通过从对角线向上或向下逐渐减去这些三角形数来计算图的其余部分,这相当于减去给定的行或列数.

注意,对角线可以正式定义为具有给定坐标总和的所有单元格的集合.例如,具有坐标和3的对角线具有坐标(0,3),(1,2),(2,1)和(3,0).因此,单个数字定义每个对角线,该数字也用于确定起始三角形数字.

因此,从简单的检查来看,计算奇数和分量的公式就是:

triangle(x + y + 1) - y

计算偶数和分量的公式很简单:

triangle(x + y + 1) - x

众所周知的三角数公式也很简单:

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

所以,算法是:

1. 初始化一个nxn数组,其中n是输入大小的平方根.
2. 计算左上部分的偶数求和坐标的索引.这可以通过嵌套两个循环来完成,一个外循环"y从0到n - 1"和一个内循环"x从y%2到y以2为步"(通过在当前y上绑定x,我们只根据需要查看左上角部分,从y%2开始,以2为步长,我们只获得偶数求和坐标.循环索引可以插入上面的公式中以获得结果.value[x, y] = triangle(x + y + 1) - x.
3. 计算左上部分的奇数求和坐标的索引.这可以通过类似的循环来实现,除了内循环将是"x从y%2 + 1到y以2的步长",以仅获得奇数求和的坐标.value[x, y] = triangle(x + y + 1) - y.
4. 通过简单的减法计算右下部分的索引,n * n + 1如本文第一部分所述.这可以通过向后计数的两个嵌套循环来完成(并且在外部循环上限定内部循环以仅获得右下部分).value[x, y] = (n * n + 1) - value[n - x - 1, n - y - 1].
5. 将网格展平为数组(排列所有行),然后将给定输入(大小为n*n)转换为输出,方法是使用网格中生成的数字作为新索引.

Answer 2

这是我的.

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;

}

用法:

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

产量

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