php выстраивают проблему поколения
Я должен случайным образом генерировать двумерный массив n на n. В этом примере, n = 10. Массив должен иметь эту структуру. Один пример:
$igra[]=array(0,1,2,3,4,5,6,7,8,9);
$igra[]=array(6,9,1,5,0,2,7,3,4,8);
$igra[]=array(2,5....................
$igra[]=array(1,7.....................
$igra[]=array(5,4...................
$igra[]=array(4,2...................
$igra[]=array(9,0.....................
$igra[]=array(8,3.....................
$igra[]=array(7,6....................
$igra[]=array(3,8....................
где
`$igra[x][z]!=$igra[y][z]` (x={0,9},y={0,9});
поскольку Вы видите, что это похоже на матрицу чисел, каждая строка его и столбец также состоят из номеров 0-9, и никогда нет времен номер два в каждой строке или в каждом столбце. как генерировать такой массив, и каждый раз случайным образом.
3 ответа
Хорошо, вот моя версия:
$n = 10;
$v1 = range(0, $n-1);
$v2 = range(0, $n-1);
shuffle($v1);
shuffle($v2);
foreach ($v1 as $x => $value)
foreach ($v2 as $y)
$array[$y][$x] = $value++ % $n;
Это должен быть действительно быстрый алгоритм, потому что он включает в себя только генерацию двух случайных массивов и вообще не требует замены местами. Он тоже должен быть случайным, но я не могу этого доказать. (По крайней мере, я не знаю, как доказать что-то подобное.)
Это оптимизированная версия очень простого алгоритма:
Сначала таким образом создается неслучайная матрица (представьте, что нам нужно только 5 * 5, а не 10 * 10):
0 1 2 3 4
1 2 3 4 0
2 3 4 0 1
3 4 0 1 2
4 0 1 2 3
В этой матрице мы теперь случайным образом меняем местами столбцы. Поскольку мы не меняем сами столбцы, ваши правила по-прежнему соблюдаются. Затем мы случайным образом меняем местами строки.
Теперь, как вы можете видеть, приведенный выше алгоритм ничего не меняет местами и не генерирует указанную выше матрицу. Это потому, что он заранее генерирует столбцы и строки для замены ( $ v1 и $ v2 ), а затем напрямую записывает в правильную позицию в результирующем массиве.
Редактировать: Только что провел сравнительный анализ: для $ n = 500 требуется 0,3 секунды.
Edit2: после замены циклов for на циклы foreach это занимает всего 0,2 секунды.
Это то, что я сделал. Сделал действительную матрицу (2d-массив), которая не является случайной. Итак, начиная с строки 0 - 0-9, строки 1 - 1-0 (т.е. 1,2,3 ... 8,9,0), строки 2 - 2-1 (2,3 ... 9, 0,1) ... строка 8 - 8-7 ... и т. Д. Затем перемешайте этот массив, чтобы рандомизировать строки, и выполните простую замену столбцов, чтобы рандомизировать столбцы. Должен получить именно то, что ты хочешь. Попробуйте следующее:
<?php
//simple function to show the matrix in a table.
function show($matrix){
echo '<table border=1 cellspacing=0 cellpadding=5 style="float: left; margin-right:20px;">';
foreach($matrix as $m){
echo '<tr>';
foreach($m as $n){
echo '<td>'.$n.'</td>';
}
echo '</tr>';
}
echo '</table>';
}
//empty array to store the matrix
$matrix = array();
//this is what keeps the current number to put into matrix
$cnt = 0;
//create the simple matrix
for($i=0;$i<=9;$i++){
for($j=0;$j<=9;$j++){
$matrix[$i][$j] = $cnt % 10;
$cnt++;
}
$cnt++;
}
//display valid simple matrix
show($matrix);
//shuffle the rows in matrix to make it random
shuffle($matrix);
//display matrix with shuffled rows.
show($matrix);
//swap the columns in matrix to make it more random.
for($i=0;$i<=9;$i++){
//pick a random column
$r = mt_rand(0, 9);
//now loop through each row and swap the columns $i with $r
for($j=0;$j<=9;$j++){
//store the old column value in another var
$old = $matrix[$j][$i];
//swap the column on this row with the random one
$matrix[$j][$i] = $matrix[$j][$r];
$matrix[$j][$r] = $old;
}
}
//display final matrix with random rows and cols
show($matrix);
?>
В моем решении, если не генерировать случайный массив и не проверять, существует ли он уже, он должен работать намного быстрее (особенно если массив когда-либо превышал 0-9). Когда вы перейдете к последней строке, есть только одна возможная комбинация чисел. Вы будете генерировать случайные массивы, пытаясь найти этот единственный ответ. Это будет почти то же самое, что выбрать число от 1 до 10 и генерировать случайное число, пока оно не достигнет того, которое вы выбрали. Это может быть с первой попытки, но опять же, вы можете выбрать 1000 случайных чисел и никогда не получить желаемое.
Хм .. Я вижу, вы уже получили несколько хороших ответов, но вот моя версия:
$n = 10;
$seed_row = range(0, $n - 1);
shuffle($seed_row);
$result = array();
for($x = 0; $x < $n; $x++)
{
$tmp_ar = array();
$rnd_start = $seed_row[$x];
for($y = $rnd_start; $y < ($n + $rnd_start); $y++)
{
if($y >= $n) $idx = $y - $n;
else $idx = $y;
$tmp_ar[] = $seed_row[$idx];
}
$result[] = $tmp_ar;
}
for($x = 0; $x < $n; $x++)
{
echo implode(', ', $result[$x]) . "<br/>\n";
}
пример вывода:
4, 3, 0, 2, 6, 5, 7, 1, 8, 9
0, 2, 6, 5, 7, 1, 8, 9, 4, 3
7, 1, 8, 9, 4, 3, 0, 2, 6, 5
2, 6, 5, 7, 1, 8, 9, 4, 3, 0
6, 5, 7, 1, 8, 9, 4, 3, 0, 2
9, 4, 3, 0, 2, 6, 5, 7, 1, 8
8, 9, 4, 3, 0, 2, 6, 5, 7, 1
5, 7, 1, 8, 9, 4, 3, 0, 2, 6
1, 8, 9, 4, 3, 0, 2, 6, 5, 7
3, 0, 2, 6, 5, 7, 1, 8, 9, 4
Он создает случайный случайный массив в качестве отправной точки Затем он проходит через начальный массив, принимая каждый элемент в качестве отправной точки для создания новой базы.