Zig-zag сканирует массив N x N

Ответ 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)
}

Ответ 2

Очень крутой вопрос. Вот анализ и алгоритм.

Ключевым преимуществом использования этого алгоритма является то, что все это делается с использованием простых целочисленных вычислений; он не имеет операторов "if" и, следовательно, не имеет ветвей, что означает, что если он был скомпилирован, он выполнялся бы очень быстро даже при очень больших значениях n. Это также означает, что его можно легко распараллелить, чтобы разделить работу на несколько процессоров на очень большие значения n.

Рассмотрим сетку 8x8 (здесь вход технически 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

Прежде всего заметим, что диагональ слева (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

Итак, алгоритм:

• Инициализировать массив n x n, где n - квадратный корень ввода размер.
• Вычислить индексы для четно-суммированных координат верхняя левая часть. Это можно сделать, вставив две петли, внешний цикл "y, идущий от 0 до n - 1", и внутренний цикл "x, идущий от y% 2 к y с шагом 2" (путем ограничения x на текущем y, мы смотрим только на верхнюю левую часть, по желанию, и, начиная с y% 2 и идя по шагам 2, мы получаем только четные координаты). Индексы цикла могут быть подключены к приведенной выше формуле для получения результатов. value[x, y] = triangle(x + y + 1) - x.
• Вычислить индексы для нечетных сумм координаты верхней левой части. Это можно сделать с помощью аналогичные циклы, за исключением внутреннего цикла, будут "x переходить от y% 2 + 1 к y с шагом 2", чтобы получить только нечетные суммы координат. value[x, y] = triangle(x + y + 1) - y.
• Вычислить индексы для нижней правой части простым вычитанием из n * n + 1, как описано в первой части этого сообщения. Это можно сделать с помощью двух вложенных циклов, отсчитывающих назад (и ограничивающих внутренний на внешнем, чтобы получить только нижнюю правую часть). value[x, y] = (n * n + 1) - value[n - x - 1, n - y - 1].
• Сгладить сетку в массив (выровняв все строки), а затем преобразовать заданный вход (размером n * n) для вывода с использованием чисел, сгенерированных в сетке, в качестве новых индексов.

Ответ 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));

Кстати, этот алгоритм называется "zig zag scan" и используется в основном для кодирования JPEG и MPEG.

Ответ 4

С одним циклом и использованием симметрии и без каких-либо ролей:

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

Ответ 5

Я написал его в С#, поэтому не компилировал/не разбирал его в 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;
        }
    }
}

Ответ 6

Пример реализации 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]

Ответ 7

Еще одно решение 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);

Здесь он находится в действии

Ответ 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;
}