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:
- Create an array of size m
- Copy m elements from original to random_subset_array
- Iterate original array from m+1 to n
- Generate random number between 0 to current_index
- If random < m then
- 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]