php array generation challenge

Question

I need to randomly generate an two-dimensional n by n array. In this example, n = 10. The array should have this structure. One example:

$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....................

where

`$igra[x][z]!=$igra[y][z]`   (x={0,9},y={0,9});

as you see it's like a matrix of numbers each row of it and column also consist from numbers 0-9, and there is never one number two times in each row or in each column. how to generate such an array, and each time randomly.

Answer 1

Okay, so here's my version:

$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;

This should be a really fast algorithm, because it involves only generating two random arrays and doesn't involve any swapping at all. It should be random, too, but I cannot prove it. (At least I don't know how to prove something like this.)

This is an optimized version of a very simple algorithm:

First a non-random matrix is created this way (imagine we want only 5*5, not 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

In this matrix we now randomly swap columns. As we don't change the columns themselves your rules still are obeyed. Then we randomly swap rows.

Now, as you can see the above algorithm doesn't swap anything and it doesn't generate the above matrix either. That's because it generates the cols and rows to swap in advance ($v1 and $v2) and then directly writes to the correct position in the resulting array.

Edit: Just did some benchmarking: For $n = 500 it takes 0.3 seconds.

Edit2: After replacing the for loops with foreach loops it only takes 0.2 seconds.