Z形扫描的N×N阵列(Zig-zag scan an N x N array)

2019-08-17 07:10发布

站内文章 / 移动开发
25 0 0

我有一个简单的数组。 数组长度总是具有整数的平方根。 所以，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:

这里是我的。 

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


Answer 2:

非常酷的问题。 这里有一个分析和算法。

使用这种算法的主要优点是，这一切都完成使用简单的整数运算; 它没有“如果”的语句，因此没有分支，这意味着如果它被编译，它甚至会在n的值非常大非常快执行。 这也意味着它可以很容易地并行划分在多个处理器的工作对于n的值非常大。

考虑8×8网格（在此，输入在技术上是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. 初始化一个n×n的阵列，其中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 3:

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

其主要特点是从其他解决方案相区别：

  • 复杂度为O的只有一个循环（N）
  • 只有基元（整数）临时变量

来源： 

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

顺便说一句，这种算法被称为“锯齿形扫描”，并正在大量用于JPEG和MPEG的编码。



Answer 4:

随着simetry并没有各种单回路和利用： 

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:

我写在C＃所以没编译/在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;
        }
    }
}


Answer 6:

还有一个PHP的解决方案，只使用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);

这是在行动



Answer 7:

例如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]


Answer 8:

这是我对了。 它类同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;
}


文章来源: Zig-zag scan an N x N array
标签： php arrays algorithm zigzag
举报

收藏的人(0)

Ta的文章 更多文章
登录 后发表评论
0条评论
还没有人评论过~