[20.3] Generate a set of m integers from an array of size n, chosen equally likely

1. Example
Equal probability


Inclusive 

(int) ( Math.random() *(higher-lower+1) ) + lower


1/n 1/n 1/n


[1] [2] [3].....[n]pick m itnegers

DON'T PICK UP TWICE => swap => the index in the subset indicating
the elements before that index has been chosen and CANNOT be  chosen again

delete element from the array=> shrinking / shifting => O(n)
subset[0] <- array[k]
==> SWAP array[0] and array[k]
subset[1]<= array[k-3]
==> SWAP array[1] and array[k-3]
...
2. Implementation

/*Random number between lower and higher, inclusive*/
/*Inclusive so we higher - lower +1 , include both end */
public static int rand(int lower, int higher)
{




    return (int) (   Math.random() *(higher-lower+1)   )   + lower;




}

/*Pick M elements from the original array. Clone original array so htat we don't destroy the input*/
public static int[] pickMRandomly(   int[] original, int m)
{




    int[] subset = new int[m];
    int[] array = original.clone();





    for (int i = 0 ; i < m; i++)
    {
         int pickIndex = rand(i, array.length -1);
         subset[i] = array[pickIndex];
         array[pickIndex] = array[i]; // array[i] is dead
    }



    return subset;

   
}

3. Similar Ones