How to get a random value from 1~N but excluding several specific values in PHP?

Question

rand(1,N) but excluding array(a,b,c,..),

is there already a built-in function that I don't know or do I have to implement it myself(how?) ?

UPDATE

The qualified solution should have gold performance whether the size of the excluded array is big or not.

Answer 1

I don't think there's such a function built-in ; you'll probably have to code it yourself.

To code this, you have two solutions :

• Use a loop, to call rand() or mt_rand() until it returns a correct value
  • which means calling rand() several times, in the worst case
  • but this should work OK if N is big, and you don't have many forbidden values.
• Build an array that contains only legal values
  • And use array_rand to pick one value from it
  • which will work fine if N is small

Answer 2

No built-in function, but you could do this:

function randWithout($from, $to, array $exceptions) {
    sort($exceptions); // lets us use break; in the foreach reliably
    $number = rand($from, $to - count($exceptions)); // or mt_rand()
    foreach ($exceptions as $exception) {
        if ($number >= $exception) {
            $number++; // make up for the gap
        } else /*if ($number < $exception)*/ {
            break;
        }
    }
    return $number;
}

That's off the top of my head, so it could use polishing - but at least you can't end up in an infinite-loop scenario, even hypothetically.

Note: The function breaks if $exceptions exhausts your range - e.g. calling randWithout(1, 2, array(1,2)) or randWithout(1, 2, array(0,1,2,3)) will not yield anything sensible (obviously), but in that case, the returned number will be outside the $from-$to range, so it's easy to catch.

If $exceptions is guaranteed to be sorted already, sort($exceptions); can be removed.

Eye-candy: Somewhat minimalistic visualisation of the algorithm.

Answer 3

The simplest way...

<?php

function rand_except($min, $max, $excepting = array()) {

    $num = mt_rand($min, $max);

    return in_array($num, $excepting) ? rand_except($min, $max, $excepting) : $num;
}
?>

Answer 4

What you need to do is calculate an array of skipped locations so you can pick a random position in a continuous array of length M = N - #of exceptions and easily map it back to the original array with holes. This will require time and space equal to the skipped array. I don't know php from a hole in the ground so forgive the textual semi-psudo code example.

1. Make a new array Offset[] the same length as the Exceptions array.
2. in Offset[i] store the first index in the imagined non-holey array that would have skipped i elements in the original array.
3. Now to pick a random element. Select a random number, r, in 0..M the number of remaining elements.
4. Find i such that Offset[i] <= r < Offest[i+i] this is easy with a binary search
5. Return r + i

Now, that is just a sketch you will need to deal with the ends of the arrays and if things are indexed form 0 or 1 and all that jazz. If you are clever you can actually compute the Offset array on the fly from the original, it is a bit less clear that way though.

Answer 5

Depending on exactly what you need, and why, this approach might be an interesting alternative.

$numbers = array_diff(range(1, N), array(a, b, c));
// Either (not a real answer, but could be useful, depending on your circumstances)
shuffle($numbers); // $numbers is now a randomly-sorted array containing all the numbers that interest you
// Or:
$x = $numbers[array_rand($numbers)]; // $x is now a random number selected from the set of numbers you're interested in

So, if you don't need to generate the set of potential numbers each time, but are generating the set once and then picking a bunch of random number from the same set, this could be a good way to go.