0
\$\begingroup\$

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);
\$\endgroup\$
4
  • 1
    \$\begingroup\$ I'm not entirely sure what you are trying to do. You want to generate how many random nubers? \$\endgroup\$
    – t3chb0t
    Nov 7, 2015 at 8:12
  • \$\begingroup\$ one random number given a range with exceptions \$\endgroup\$ Nov 7, 2015 at 8:30
  • 1
    \$\begingroup\$ 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? \$\endgroup\$
    – t3chb0t
    Nov 7, 2015 at 8:36
  • \$\begingroup\$ 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. \$\endgroup\$ Nov 7, 2015 at 9:05

2 Answers 2

3
\$\begingroup\$

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.
\$\endgroup\$
2
  • \$\begingroup\$ The back slashes and dollar signs make your text hard to read, thanks though. \$\endgroup\$ Nov 7, 2015 at 10:07
  • 1
    \$\begingroup\$ @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? \$\endgroup\$
    – Martin R
    Nov 7, 2015 at 10:09
2
\$\begingroup\$

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;
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.