Зигзагообразное сканирование массива N x N
У меня есть простой массив. Длина массива всегда имеет квадратный корень из целого числа. Итак, 16, 25, 36 и т. Д.
$array = array('1', '2', '3', '4' ... '25');
Я делаю массив с HTML, чтобы он выглядел как блок с четными сторонами.
То, что я хочу сделать, это отсортировать элементы, чтобы при передаче массива, закодированного в JSON, в jQuery он выполнял итерацию массива, затемнялся в текущем блоке, и поэтому я получал своего рода волновую анимацию. Так что я хотел бы отсортировать массив вроде этого
Так что мой отсортированный массив будет выглядеть
$sorted = array('1', '6', '2', '3', '7', '11', '16, '12' .. '25');
Есть ли способ сделать это?.. Спасибо
10 ответов
Вот мой.
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.
Рассмотрим сетку 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) в выход, используя числа, сгенерированные в сетке, в качестве новых индексов.
С одной петлей и с использованием симетрии и без сортировок:
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));
Хотя уже есть много решений этого вопроса, это мое:
Главная особенность, которая отличает его от других решений:
- Только один цикл сложности 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.
Еще одно 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);
Это код, который я написал для одного из своих заданий при реализации JPEG.
Приведенный ниже код считывает следующий образец матрицы следующим образом:
[[1, 2, 3],
[4, 5, 6], -> [1, 2, 4, 7, 5, 3, 6, 8, 9]
[7, 8, 9]]
Опубликованный вопрос хочет прочитать его другим зигзагообразным способом, но это можно сделать с помощью нескольких настроек моего кода ниже. Надеюсь это поможет :)
def read_zigzag_n(patch, N):
output = []
s = 1 # max number of entries in diagonal of that iteration
i = 0
j = 0
# flip = 0 -> row++ col-- ; flip = 1 -> row-- col++
flip = 1 # initially setting would be this because from 0,0 need to go to 0,1
# reading left upper triangle
while s < N+1:
count = 0 # counts the number of entries added from current diagonal
if flip == 0:
while(count<s-1): # s-1 because after last entry only one of row or col incremented
output.append(patch[i,j])
count += 1
i += 1
j -= 1
output.append(patch[i,j])
i += 1
flip = 1
else:
while(count<s-1):
output.append(patch[i,j])
count += 1
j += 1
i -= 1
output.append(patch[i,j])
j+=1
flip = 0
s += 1
# at this point s = N+1,
# and one of i or j is N and 0 respectively, depending on if N even or odd
if N % 2 == 0:
i -= 1
j += 1
flip = 1
else:
i += 1
j -= 1
flip = 0
s -= 2 # because now diagonal contains N-1 entries
# reading right lower triangle
while s > 0:
count = 0
if flip == 0:
while(count<s-1):
output.append(patch[i,j])
count += 1
i += 1
j -= 1
output.append(patch[i,j])
j += 1 # now its j += 1 instead of i += 1
flip = 1
else:
while(count<s-1):
output.append(patch[i,j])
count += 1
j += 1
i -= 1
output.append(patch[i,j])
i+=1 # now its i += 1 instead of j += 1
flip = 0
s -= 1
return output
Это реализация на питоне
def zigZagEncoding(M):
r, c = M.shape
zigZag = [[] for i in range(r+c-1)]
for i in range(r):
for j in range(c):
Sum = i+j
if (Sum %2 != 0):
zigZag[Sum].insert(0, M[i,j])
else:
zigZag[Sum].append(M[i,j])
arranged = []
for i in zigZag:
for j in i:
arranged.append(j)
return arranged
Вход:
M = np.array([[1,2,3,4,5],[6,7,8,9,10],[11,12,13,14,15],[16,17,18,19,20],[21,22,23,24,25]])
zigZagEncoding(M)
Выход:
[1, 6, 2, 3, 7, 11, 16, 12, 8, 4, 5, 9, 13, 17, 21, 22, 18,
14, 10, 15, 19, 23, 24, 20, 25]
Я написал это на 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;
}
}
}
Пример реализации 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]
Это мое мнение. Это похоже на ответ Квинта, но более кратко.
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;
}