Randomly generate m integers from an array of size n

Problem

Write a method to randomly generate a set of m integers from an array of size n Each element must have equal probability of being chosen.

Solution

This question depends on 2 things:

• how random number generation works?
• Fisher yates algorithm or Knuth Shuffle?

Now that we have fisher yates algorithm in our quiver, we can solve this problem :

let m be the number of elements to select
for i = 1; i <= m; i++
   pick a random number from 1 to n, call it j
   swap array[j] and array [n] (assuming 1 indexed arrays)
   n-- 

public static int[] chooseNFromM(int[] array, int m) {
    if (m > array.length)
        return null;
    int[] results = new int[m];
    for (int i = 0; i < m; ++i) {
        int index, temp;
        do {
            index = new Random().nextInt(array.length);
        } while (index < i);
        temp = array[index];
        array[index] = array[i];
        array[i] = temp;
    }
    for (int i = 0; i < m; ++i) {
        results[i] = array[i];
    }
    return results;
}

We don't need to keep generating random numbers. We just need to label which ones are 'dead' (in this case, 0 to i) and generate random index in the valid range (i+1 to n).
We should first make an copy of the original array as we don't want to modify it.

References

• http://tianrunhe.wordpress.com/2012/06/04/randomly-generate-m-integers-from-an-array-of-size-n/
• http://stackoverflow.com/questions/6251626/choosing-a-subset-in-uniformly-random-manner