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

Вот моя.

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

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

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

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

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

1. Инициализируйте массив nxn, где n – квадратный корень из входного размера.
2. Вычислите индексы для четных координат верхней левой части. Это может быть выполнено путем вложенности двух циклов, внешнего цикла «y, идущего от 0 до n – 1», и внутреннего цикла «x, идущего от y% 2 до y с шагом 2» (путем ограничения x на текущий y, мы смотрим только на верхнюю левую часть, если хотите, и, начиная с 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) на вывод, используя числа, сгенерированные в сетке, как новые индексы.

Хотя на этот вопрос уже много решений, это мое:

Основная особенность, которая отличает его от других решений:

• Только один цикл сложности 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.

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

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