8

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.

Improve this question
3
  • sorry, nothing . just when copied and translated from other forum I have forgotten to delete it Commented Jul 18, 2010 at 8:16
  • You mean a Sudoku solver/generator? Commented Jul 18, 2010 at 8:17
  • it's actually not sudoku. it's 10 question's which should be assigned to 10 persons in a manner that no 2 persons will get the same question in the same level. Sudoku table of numbers will do , but without rule that in each 3x3 block also we should have 1-9.... Commented Jul 18, 2010 at 8:19

3 Answers 3

Reset to default
8

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

7 Comments

the solution you provide also gives a table as i need. Thank you also!
if you wanted to randomize the rows, you could just do a shuffle($array) at the end. This is essentially the same as mine except that I do rows then cols and you do cols then rows. However this will be faster (as you said) because your solution doesn't swap as mine does. Nice.
Yep, seems to be same algorithm with different implementation. Tried yours, too, it took 1.0 seconds for 500x500, that's three times slower than mine. On the other hand: Yours can be understood right away, whereas mine requires some paper ^^
yes, tested both mine and yours with $n=500 to compare and yours was .3 seconds and mine ran in .7 so over a 50% drop.
what about the case when I have 10 questions for 17 players and I need at least 1 time any question to be given for 2 groups???? I mean nXn table lets say 10X10 is for a case when i have 10 questions and in each round a group or player gets one question, and the matrix gives possibility to make sure that no 2 players get the same question at time. What if we have 10>17 case? 10 questions for 17 players? I mean when the case is not nXn but nXm where n<m , there it's obvious that I should have 0-10 + 7 rundom numbers. But I need again that minimum overlaps take place?????
|
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.

Improve this answer

1 Comment

works like a charme! Thank you. I will need to modifiy it a little,to use in my code, but it's super!thanks Jonathan!
0

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.

Improve this answer

5 Comments

But this isn't random at all. I you know the first row and the first element of the second row, then you know the whole second row.
The question states that 'there is never one number two times in each row or in each column. how to generate such an array, and each time randomly.' That is exactly what this does :)
And still it isn't really "random".
well, it might be algorithmic and not cryptographically strong, but as long as the seed is random you will get random results. i do not really understand your complaints, it completely satisfies the requirements. also, the algorithm is pretty fast and scales linearly as far as i can tell.
agreed, not really random. The first row is random. but every row after that is just the same thing shifted a little. If you take the sample, first row you have the numbers: 4302657189. if you find the row that starts with the second number, you get 3026571894. its the exact same order except the first number (4) is now on the end. it's essentially shifted by 1. If this is for questions (like on a test), once you line up one question, the rest are in the same order after that.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.