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.

Answer 2

This is what I did. Made a valid matrix (2d array) that isn't random. So starting out, row 0 is 0-9, row 1 is 1-0 (ie: 1,2,3...8,9,0), row 2 is 2-1 (2,3...9,0,1)...row 8 is 8-7...etc. Then shuffle that array to randomize the rows and perform a simple column swap to randomize the columns. Should get back exactly what you want. Try this:

<?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);
?>

In my solution, by not generating a random array and checking if it already exists, it should run much faster (especially if the array ever went above 0-9). When you get down to the last row, there is only one possible combination of numbers. You will be generating random arrays trying to find that one answer. It would be pretty much the same as picking a number from 1 to 10 and generating a random number until it hits the one you picked. It could be on the first try, but then again you could pick 1000 random numbers and never get the one you wanted.

Answer 3

Hmm.. I see you got some good answers already, but here's my version:

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

sample output:

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

It creates a random random array as a starting point Then it walks through the seed array taking each element as a starting point for itself to create a new base.