Random integer range with exceptions

Question

I have to generate a random number from a range with exceptions held in a bool array, is there a way to do it without a loop depending on probability? There is also a potential infinite loop here if all values are false. Any suggestions?

    bool[] paths = InnateChannels(channelID, channelOrientation);

    bool done = false;
    int iDirection = 0;
    while (!done)
    {
        iDirection = Random.Range(0, 4);
        if (paths[iDirection])
            done = true;
    }
    direction = DirectionToVector(iDirection);

Answer 1

As you already noticed, your code will loop forever if all array elements are false, so you have to check first if at least one element is true.

If the array has \$ N \$ elements with \$ t \$ of them being true, then the probability that a random number in the range \$ 0 ... N-1 \$ is "valid" is \$ t/N \$. This means that the expected number of iterations is \$ N/t \$. For example, if half of the possible directions are valid, you'll need 2 iterations in average. If only 1% are valid, you'll need 100 iterations in average.

Here is a possible alternative which needs only a single random number. As I am not so familiar with C#, I'm describing the algorithm only.

• Count the number \$ t \$ of true elements in the array. Terminate if \$ t = 0 \$.
• Compute a random number \$ i \$ in the range \$ 1 ... t \$.
• Traverse the array once to find the \$i^\text{th} \$ entry which is true. The index of that element is your result.

Answer 2

You write in your comment

So paths[0], paths[1], paths[3], paths[6] are true, that means I want the method to generate a random number from 0,1,3,6. [...].

You can achieve this with LINQ:

// a few test values
var paths = new[] { true, true, false, true, false, false, true };

// initialize random numbers generator
var rnd = new Random((int)DateTime.Now.Ticks);

// get a random number for each 'true' value
var randomNumber = paths.Where(p => p).Select(p => rnd.Next(0, 4)).ToArray();

---

Remember to use constants instead of magic numbers:

const int minNumber = 0;
const int maxNumber = 4;