Non-Uniform randomizer

Question

I need to to generate 6 unique random numbers from 1 to 37; At first I used a simple array mapping:

private int k=6, n=37;

public int[] Results ()
{
    // fill an array with numbers 1 2 3 . . . n
    int[] numbers = new int[n];
    for (int i = 0; i < numbers.length; i++)
        numbers[i] = i + 1;

    // draw k numbers and put them into a second array
    int result[] = new int[k];
    for (int i = 0; i < result.length; i++)
    {
        // make a random index between 0 and n - 1
        int r = (int) (Math.random() * n);
        // pick the element at the random location
        result[i] = numbers[r];
        // move the last element into the random location
        numbers[r] = numbers[n - 1];
        n--;
    }
    return result;
}

The problem was that in a lot of the cases I got a near uniformic distribution (escpicially when I make less then 10 draws) i.e.: 1,9,16,18,24,30 or 5,16,18,22,26,29

What I really need is a TRUE randomizer that can give me results like: 11,16,25,29,30,32 or 4,8,9,15,18,19 in LESS then 10 draws.

I saw also a HashMap implementation of something similar:

import java.util.*;

public class RandomHash
{
    HashMap numbers = new HashMap() ;
    Random rnd_gen = new Random() ;

    RandomHash()
    {
        for(;;)
        {
            int rnd_num = rnd_gen.nextInt() ;
            Integer rnd_num_obj = new Integer(rnd_num) ;

            if (! numbers.containsKey(rnd_num_obj) )
            {
                numbers.put(rnd_num_obj, rnd_num_obj) ;
                /* Do whatever with the number */
                break ;
            } /* else loop and get another rnadom num */

        } /*end for*/
    }
}

The problem is that I currently don't know how to bound the randomizer and the hashmap to 6 and 32 respectively. Will the hashmap give more scrambled results ?

Answer 1

I would just shuffle the first array (after the initialization step) and take the top 6 elements. You can use something like

Collections.shuffle( Arrays.asList(array) );

to shuffle the array with built-in functions of the language.

If you were choosing from 1,000,000 elements it might be a performance issue, but with only 37 I think shuffling is a clearer solution.

Answer 2

You can do it in one random number call! 10 is nine too many :-)

Notice that there are exactly 37 choose 6 possibilities for your 6 numbers.

So, all you need to do is choose a random number between 1 and 2324784 (which is 37 choose 6).

Then use a mapping to get the coressponding combination of 6 elements. For an example of a mapping see here:Generating the mth Lexicographical Element of a Mathematical Combination.

A Java port of the MSDN code is here: http://the-lost-beauty.blogspot.com/2010/07/generating-combinations-in.html

Answer 3

You ask for random numbers and that is what you get. Your two examples: 11,16,25,29,30,32 and 4,8,9,15,18,19 are simply less probable than the results you seem to think are evenly distributed.

Let us for example look at your last result and for simplification say that you expect all numbers to be less or equal to 19. If you choose a single number between 1 and 32, you have a 19/32 chance (appr 59%) for it to be 19 or less. If you choose 6 distinct numbers between 1 and 32, there is less than 3% chance for all of these to be 19 or less.

When running your code 100 times, I actually got five lists fulfilling the requirement, which is two more than statistically expected:

[3, 8, 13, 16, 18, 19]

[2, 3, 6, 8, 10, 14]

[2, 6, 7, 8, 13, 18]

[4, 5, 9, 10, 11, 12]

[8, 12, 13, 15, 16, 17]

Answer 4

Linear congruential generator modulo 37, with suitably chosen parameters?

Alternatively,

List l = Arrays.asList(numbers);
Collections.shuffle(l);
return l.subList(0,k).toArray();

Note that it expects numbers to be an Object[] and returns another Object[].

Answer 5

Here's a non-uniform distribution:

return new int[]{1,2,3,4,5,6};