Задача создания массива php

Question

Мне нужно случайным образом сгенерировать двумерный массив 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, и никогда не бываетчисло два раза в каждой строке или в каждом столбце.как генерировать такой массив, и каждый раз случайным образом.

Answer 1

Хорошо, вот моя версия:

$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 секунды.

Answer 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 случайных чисел и никогда не получить желаемое.

Answer 3

Хм .. Я вижу, вы уже получили несколько хороших ответов, но вот моя версия:

$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

Создает случайный случайный массив в качестве отправной точки. Затем он проходит через начальный массив, принимая каждый элемент в качестве отправной точки для создания новой базы.