CODEWITHSUNDEEP
phpalgorithm
NameX
NameX

Reputation: 59

Filling grid/array randomly

I've array MxN of zeros (0). I need to fill it with 20 truths (1) by random postions.

An example

1 1 1 0 1 0 1 
0 0 0 0 0 0 0 
0 1 0 1 0 1 1 
0 0 0 0 1 1 1 
0 0 1 0 0 0 0 
0 0 1 0 1 1 0 
1 1 0 1 1 0 0

I fill it by non-determine algorithm:

$amountUnits = 20;
while($amountUnits > 0) {
    $i = rand(0, $M-1);
    $j = rand(0, $N-1);

    if(!$grid[$i][$j]) {
        $grid[$i][$j] = 1;
        $amountUnits--;
    }
}

But it's solved in random time. How can I fill it throught seed or something else? And where I can read about this problem?

Please excuse my bad English.

Thank you!

Upvotes: 0

Views: 479

Answers (3)

Jared Farrish
Jared Farrish

Reputation: 49188

It seems like you could do this (since it's really just a chopped up string of random digits?):

function truths(int $truths, int $many): array {
    $facts = array_fill(0, $truths, true);
    $statements = array_fill(0, $many, false);

    foreach ($statements as $assertion => $statement) {
        $statements[$assertion] = $facts[$assertion] ?? false;
    }

    shuffle($statements);

    return $statements;
}

Then you give a function the number of truths and grid dimensions, and it will generate the output:

function truth_grid(int $truths, int $rows, int $columns) {
    return chunk_split(implode(' ', array_map('intval',
        truths($truths, $rows * $columns)
    )), $columns * 2);
}

Given:

$set = [[4, 3, 3], [10, 4, 5], [12, 3, 9], [5, 2, 10],];

foreach($set as [$truths, $rows, $columns]) {
    print_r(
        sprintf('%d of %d x %d', $truths, $rows, $columns).PHP_EOL.PHP_EOL.
        truth_grid($truths, $rows, $columns).PHP_EOL
    );
}

The readout of which is:

4 of 3 x 3

1 0 0 
1 0 1 
1 0 0

10 of 4 x 5

1 0 0 0 1 
0 1 0 0 1 
1 1 0 0 0 
1 1 1 0 1

12 of 3 x 9

0 0 0 0 1 1 0 0 0 
0 0 0 1 1 1 1 0 1 
1 1 1 0 0 1 0 0 1

5 of 2 x 10

0 0 0 0 0 0 0 0 1 1 
0 0 1 0 0 0 1 0 0 1

And if you're looking for chunked arrays of the same shape:

function truth_chunks(int $truths, int $rows, int $columns) {
    return array_chunk(truths($truths, $rows * $columns), $columns);
}

Upvotes: 0

Jim Mischel
Jim Mischel

Reputation: 133950

Updated

So it turns out that PHP has a shuffle function, and @jspit's answer shows you how to use it. His answer is the php way to implement my answer.

Original Answer

Fill the array with 0's, and then add all of the 1's in the first rows and columns. So if you have an array that's 4 rows and 5 columns, and you want 7 1's, it would look like this:

1 1 1 1 1
1 1 0 0 0
0 0 0 0 0
0 0 0 0 0

Now, do a Fischer-Yates shuffle to distribute the 1's around randomly.

Normally, you do that shuffle on a 1-dimensional array. But you can map a 1-dimensional array index to two dimensions with some simple arithmetic, as shown below in pseudo-code. (Sorry, but I'm not really fluent in php.)

// shuffle a 2-dimensional array
for (i = numRows * numCols; i > 1; --i)
    j = random(0, i)  // picks a number from 0 to i-1

    // get row and column for i
    irow = (i-1) / numCols  
    icol = (i-1) % numCols

    // get row and column for j
    jrow = j / numCols
    jcol = j % numCols

    // and swap the items
    temp = array[irow, icol]
    array[irow, icol] = array[jrow, jcol]
    array[jrow, jcol] = temp

Upvotes: 0

jspit
jspit

Reputation: 7683

Fill a 1-dimensional array x times with 1 and the rest with 0. shuffle () shuffles the array. array_chunk divides the array so that a matrix (a 2-dimensional array) is created.

$rows = 7;
$cols = 7;
$fillTrue = 20;

$arr = array_fill(0,$fillTrue,1)+array_fill($fillTrue, $rows*$cols-$fillTrue,0);
shuffle($arr);
$arr = array_chunk($arr,$cols);

Upvotes: 2

Related Questions