get 4 random numbers

Question

I need generate 4 different random numbers, with given range. Like this:

define('min', 3000);
define('range', 6000);
define('diff', 200);

$array[0] = rand(min ,min + range);
$array[1] = rand(min ,min + range);
while(abs($array[0]-$array[1])<diff)
    $array[0] = rand(min ,min + range);
$array[2] = rand(min ,min + range);
while((abs($array[2]-$array[0])<diff)
    ||(abs($array[2]-$array[1])<diff))
    $array[2] = rand(min ,min + range);
$array[3] =rand(min ,min + range);
while((abs($array[3]-$array[0])<diff)
    ||(abs($array[3]-$array[1])<diff)
    ||(abs($array[3]-$array[2])<diff))
    $array[3] = rand(min ,min + range);

Is there any way to optimize this algorithm?

Answer 1

First, you might want to state that you want four random numbers within the same interval but with a minimum distance to each other (as the code does). Your current method involves looping, possibly indefinitely, but probably just for a while, until those numbers are reached.

So long as you only need four random numbers, it does not really matter much if you do it like this. It could be written more generically, allowing the natural extension of drawing more numbers than four, but that will not necessarily make it any faster, even for four numbers.

Assuming you want an upper bound on the time it takes (which your current code only gives with some probability), here is an algorithm that will work (so long as the interval is large enough): Draw a random number N and create two partitions of the interval, one for valid subsequent numbers lower than N and one for valid subsequent numbers higher than N. For each subsequent random number, pick an available partition at random and continue in the same fashion.

This runs in O($n) if you disregard the time count($intervals) takes (it could take O(1), but it gets a little uglier). I cannot say that this algorithm produces numbers with the same probability distribution as your initial algorithm. One thing that suggests that the probability distribution is biased: A partition is chosen at random with equal weight, not based on how large the interval is.

<?php

function random_interval($n, $min, $max, $distance) {
    $result = array();
    $intervals = array(array($min, $max));
    while ($n-- > 0 && count($intervals) > 0) {
        // find a random, valid interval
        $i = array_rand($intervals);

        // extract this interval
        $cur_min = $intervals[$i][0];
        $cur_max = $intervals[$i][1];
        unset($intervals[$i]);

        // find a random value within this interval
        $r = rand($cur_min, $cur_max);
        $result[] = $r;

        // if there are valid intervals before and after $r,
        // add these intervals back to the set of intervals
        if ($r - $distance > $cur_min)
            $intervals[] = array($cur_min, $r - $distance);
        if ($r + $distance < $cur_max)
            $intervals[] = array($r + $distance, $cur_max);
    }
    return $result;
}

Answer 2

When you generate the nth number, generate it within the range (min, min+range-2*diff*(n-1)), then iterate through the previous numbers, and if the currently generated number is "blocked" by the previous number, add 2*diff to it. Here is the code that does that, but also considers situations where a previously generated number is close to the bounds (in this case, you dont need to add 2*diff to the newly generated number, only a smaller amount):

define('min', 3000);
define('range', 6000);
define('diff', 200);

$numbers = array();
$bounds = array();

for($i = 0; $i<4; $i++){
    $min = min;
    $range = range;
    foreach($bounds as $amount){
        $range -= $amount;
    }
    $rnd = rand($min, $min + $range);
    foreach($bounds as $position => $amount){
        if($position <= $rnd){
            $rnd += $amount;
        }
        else{
            break;
        }
    }
    $numbers[$i] = $rnd;
    if($rnd <= min + diff){
        $bounds['0'] = $rnd - min + diff; 
    }
    elseif($rnd >= min + range - diff){
        $bounds[strval($rnd-diff)] = min + range - $rnd + diff;
    }
    else{
        $bounds[strval($rnd-diff)] = 2 * diff;
    }
    ksort($bounds);
}
print_r($numbers);

Its not to optimized, it runs in O(n^2log(n)), even thought O(nlog(n)) would be possible.