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:

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

Problem

Solution

See also