Generate Random Subset from Set

Generate Random Subset from Set

From given set of size n generate random subset of size m, where each element must have equal probability of being chosen.
Algorithm:
  1. Create an array of size m
  2. Copy m elements from original to random_subset_array
  3. Iterate original array from m+1 to n
    1. Generate random number between 0 to current_index
    2. If random < m then
      1. Swap current_index element with random index in random_subset_array

Latest Source Code:
Github: RandomSubSet.java


Output:

Set: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
SubSet(3): [1, 2, 7]
SubSet(5): [1, 2, 7, 9, 6]
SubSet(4): [9, 2, 6, 4]
Author: Hrishikesh Mishra