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);

• t3chb0t: I'm not entirely sure what you are trying to do. You want to generate how many random nubers?
• Omar Chehab: one random number given a range with exceptions
• t3chb0t: What do you mean by a range with exceptions? Let's say the paths array contains these values: { true, true, false, true, false, false, true }- how many random number do expect from it? Currently it's a totaly random result but apperently you don't want it like that so what would be the correct result?
• Omar Chehab: 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. Sorry if I am unclear, I had to rush it since I was leaving for a bit.

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.

• Omar Chehab: The back slashes and dollar signs make your text hard to read, thanks though.
• Martin R: @OmarChehab: You are welcome! – The backslashes and dollar signs make the text render as LaTeX formulas, see codereview.stackexchange.com/editing-help#latex. Perhaps that does not work in your browser?

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;