Z形扫描N×Narrays

我有一个简单的数组。 数组长度总是有一个整数的平方根。 所以16,25,36等 

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

我所做的，就是用HTML来排列数组，使它看起来像是一个双面的块。

我想要做的是对元素进行sorting，以便当我将JSON编码数组传递给jQuery时，它将迭代数组，淡入当前块，从而得到一种波animation。 所以我想sorting这样的数组types

所以我的sorting数组看起来像 

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

有办法吗？谢谢

这是我的。 

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

非常酷的问题。 这是一个分析和一个algorithm。

使用这种algorithm的一个关键优势是它全部使用简单的整数计算完成; 它没有“if”语句，因此没有分支，这意味着如果它被编译，即使对于非常大的n值，它也会执行得非常快。 这也意味着可以很容易地将工作分成多个处理器以获得非常大的n值。

考虑一个8×8的网格（在这里，input在技术上n = 64，但为了简单起见，下面我将使用n = 8）跟在这个曲折模式之后，就像这样（使用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

首先注意到从左下angular（0,7）到右上angular（7,0）的对angular线将网格分成两个近似镜像的分量： 

  [ 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

你可以看到右下angular是左上angular的镜像，从正方形加上1（这种情况下是65）中减去。

如果我们可以计算左上angular的部分，那么右下部分可以很容易地通过取正方形加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 。

但是我们仍然需要计算左上angular的部分。 请注意，这也可以进一步细分为两个重叠的组件，其中一个组件的数字随着右上angular的增加而增加： 

  [ 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 ）之和为奇数的数字，后者定义为坐标之和为偶数的数字。

现在，关键的洞察是，我们在这里画三angular形，所以三angular形数字在这里起着突出的作用。 三angular形序号是：1,3,6,10,15,21,28,36 …

正如你所看到的，在奇数和分量中，第一行（3,10,21,36）出现了以3开始的其他每个三angular形数字，在偶数和分量中，每隔一个以1开始的三angular形数字出现在第一列（1,6,15,28）。

具体而言，对于给定的坐标对（x，0）或（0，y），对应的三angular形数字是三angular形（x + 1）或三angular形（y + 1）。

而其余的图可以通过递增地从这些三angular形数字减去对angular线来计算，这相当于减去给定的行数或列数。

请注意， 对angular线可以正式定义为具有给定坐标和的所有单元格的集合。 例如，坐标和3的对angular线具有坐标（0,3），（1,2），（2,1）和（3,0）。 所以一个数字定义了每个对angular线，这个数字也被用来确定起始三angular形数字。

所以从简单的检查来看，计算奇数和分量的公式就是： 

 triangle(x + y + 1) - y

而计算偶数和分量的公式简单地说就是： 

 triangle(x + y + 1) - x

众所周知的三angular数字公式也很简单： 

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

那么，algorithm是：

  1. 初始化一个nxn数组，其中n是input大小的平方根。
  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. 将网格平铺到一个数组中（排列所有的行），然后通过使用网格中生成的数字作为新的索引来将给定的input（大小为n * n）转换为输出。

虽然这个问题已经有很多解决scheme，但这是我的：

与其他解决scheme区别的主要特征：

  • 只有一个复杂的循环O（n）
  • 只有原始（整数）的临时variables

来源： 

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

顺便说一下，这种algorithm被称为“锯齿形扫描（zig zag scan）”，并被大量用于JPEG和MPEG编码。

通过一个循环，利用测光，没有任何sorting： 

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

我用C＃编写它，所以没有编译/parsing它在PHP中，但这个逻辑应该工作： 

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

PHP版本看起来像这样： 

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

另外一个PHP解决scheme，只for if ，只遍历数组一次 

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

这是在行动

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

输出： 

 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

喜剧一线实施： 

 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)

输出： 

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

这是我的承担。 它类似于qiuntus的反应，但更简洁。 

 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; }
Interesting Posts