Expand a random range from 1–5 to 1–7

by

This is equivalent to Adam Rosenfield’s solution, but may be a bit more clear for some readers. It assumes rand5() is a function that returns a statistically random integer in the range 1 through 5 inclusive.

int rand7()
{
    int vals[5][5] = {
        { 1, 2, 3, 4, 5 },
        { 6, 7, 1, 2, 3 },
        { 4, 5, 6, 7, 1 },
        { 2, 3, 4, 5, 6 },
        { 7, 0, 0, 0, 0 }
    };

    int result = 0;
    while (result == 0)
    {
        int i = rand5();
        int j = rand5();
        result = vals[i-1][j-1];
    }
    return result;
}

How does it work? Think of it like this: imagine printing out this double-dimension array on paper, tacking it up to a dart board and randomly throwing darts at it. If you hit a non-zero value, it’s a statistically random value between 1 and 7, since there are an equal number of non-zero values to choose from. If you hit a zero, just keep throwing the dart until you hit a non-zero. That’s what this code is doing: the i and j indexes randomly select a location on the dart board, and if we don’t get a good result, we keep throwing darts.

Like Adam said, this can run forever in the worst case, but statistically the worst case never happens. 🙂

More Related Contents:

  1. Unique (non-repeating) random numbers in O(1)?
  2. How to find list of possible words from a letter matrix [Boggle Solver]
  3. Is there an efficient way to generate N random integers in a range that have a given sum or average?
  4. What distribution do you get from this broken random shuffle?
  5. How to find all combinations of coins when given some dollar value [closed]
  6. Select k random elements from a list whose elements have weights
  7. Data structures for loaded dice?
  8. Finding a single number in a list [duplicate]
  9. Pseudorandom Number Generator – Exponential Distribution
  10. Algorithm to generate anagrams
  11. How to generate Sudoku boards with unique solutions
  12. Choosing n numbers with fixed sum
  13. Shuffle list, ensuring that no item remains in same position
  14. True random number generator [closed]
  15. Efficiently reverse the order of the words (not characters) in an array of characters
  16. Create a random permutation of 1..N in constant space
  17. Programming Riddle: How might you translate an Excel column name to a number?
  18. Creating a random number generator from a coin toss
  19. Given a number, produce another random number that is the same every time and distinct from all other results
  20. Fastest algorithm for circle shift N sized array for M position
  21. Random points inside a parallelogram
  22. Reservoir sampling
  23. Generating shuffled range using a PRNG rather than shuffling
  24. Randomly choosing from a list with weighted probabilities
  25. A Good and SIMPLE Measure of Randomness
  26. Unbiased random number generator using a biased one
  27. How to print all possible balanced parentheses for an expression?
  28. Best way of calculating n choose k?
  29. Finding multiple entries with binary search
  30. Given a number, find the next higher number which has the exact same set of digits as the original number

Leave a Comment