私は単純な配列を持っています。配列の長さは常に整数の平方根になります。つまり、16、25、36 などです。
$array = array('1', '2', '3', '4' ... '25');
私がしていることは、配列をHTMLで配置して、側面が偶数のブロックのように見えるようにすることです。
私がやりたいのは、要素を並べ替えることです。JSON でエンコードされた配列を jQuery に渡すと、配列が反復され、現在のブロックにフェードインされ、一種のウェーブ アニメーションが得られます。だから私はこのような配列をソートしたいと思います
したがって、ソートされた配列は次のようになります
$sorted = array('1', '6', '2', '3', '7', '11', '16, '12' .. '25');
そうする方法はありますか?..ありがとう
とてもクールな質問です。これが分析とアルゴリズムです。
このアルゴリズムを使用する主な利点は、単純な整数計算を使用してすべてが行われることです。「if」ステートメントがないため、分岐がないため、コンパイルされた場合、n の値が非常に大きい場合でも非常に高速に実行されます。これは、n の値が非常に大きい場合に、複数のプロセッサ間で作業を分割するために簡単に並列化できることも意味します。
8x8 グリッド (ここでは、入力は技術的には n = 64 ですが、以下の式では簡単にするために n = 8 を使用します) を考えてみます。
[ 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) への対角線が、グリッドを 2 つのミラーに近いコンポーネントに分割していることに注意してください。
[ 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) から差し引いたものであることがわかります。
左上の部分が計算できれば、右下の部分は、2 乗に 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) の値は 1765 - 17 == 48です。
しかし、左上の部分を計算する必要があります。これは、2 つの重複するコンポーネントにさらに細分化することもできます。1 つのコンポーネントは、右に向かうにつれて数字が増加します。
[ 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
そして、左下に向かうにつれて数字が増加する 1 つのコンポーネント:
[ 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 で始まる 1 つおきの三角数が最初の行 (3、10、21、36) に表示され、偶数和コンポーネントでは、1 で始まる 1 つおきの三角数が表示されます。最初の列 (1、6、15、28)。
具体的には、特定の座標ペア (x,0) または (0,y) に対応する三角形番号は、三角形 (x + 1) または三角形 (y + 1) です。
そして、グラフの残りの部分は、これらの三角形の数から対角線を上または下に徐々に減算することで計算できます。これは、指定された行または列の番号を減算することと同じです。
対角線は、指定された座標の合計を持つすべてのセルのセットとして正式に定義できることに注意してください。たとえば、座標の合計が 3 の対角線の座標は (0,3)、(1,2)、(2,1)、および (3,0) です。したがって、1 つの数値が各対角線を定義し、その数値は開始三角数を決定するためにも使用されます。
したがって、簡単な調査から、奇数和コンポーネントを計算する式は次のようになります。
triangle(x + y + 1) - y
偶数和コンポーネントを計算する式は次のとおりです。
triangle(x + y + 1) - x
また、よく知られている三角形の数の公式も単純です。
triangle(n) = (n * (n + 1)) / 2
したがって、アルゴリズムは次のとおりです。
value[x, y] = triangle(x + y + 1) - x.value[x, y] = triangle(x + y + 1) - y.n * n + 1この投稿の最初の部分で説明したように、から単純に減算して、右下部分のインデックスを計算します。これは、逆方向にカウントする 2 つのネストされたループで実行できます (そして、内側のループを外側のループにバインドして、右下部分のみを取得します)。value[x, y] = (n * n + 1) - value[n - x - 1, n - y - 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)
}
単一のループを使用し、サイメトリを利用し、ソートなしで：
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));
この質問にはすでに多くの解決策がありますが、これは私のものです。
他のソリューションとの主な違いは次のとおりです。
起源：
<?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の符号化に多用されています。
forとのみを使用するもう 1 つの PHP ソリューションは、if配列を 1 回だけトラバースします。
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);
私は 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;
}
}
}
これが私の見解です。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;
}
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
コメディ 1 行の実装:
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]