Randomly generate a set of m integers from an array of size n
probability, random
Solution
Think about it like you're picking `m` random numbers from a bag of `n` numbers, with the first `j` elements representing `the numbers in your hand` and the remaining elements representing `the numbers still in the bag`. (You iterate `j` from 0 to `m - 1` to pull out numbers, as your book suggests. `j`, then, represents the number of integers that you have already pulled out of the bag.)
If you're picking `m` integers from a bag in real life, then every time you pick a new number, you take from the bag only and not from your hand. Thus, the `remaining_num_elements` shrinks at each step.
When you think this way, it should be simple to see that this method guarantees that each element has equal probability of being chosen.
Problem
Full Question is: 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` This question is picked from "Crack the coding interview" and the solution is this: We can swap the element with an element at the beginning of the array and then “remember” that the array now only includes elements `j` and greater. That is, when we pick `subset[0]` to be `array[k]`, we replace `array[k]` with the first element in the array. When we pick `subset[1]`, we consider `array[0]` to be “dead” and we pick a random element `y` between 1 and array `size()`. We then set subset[1] equal to `array[y]`, and set `array[y]` equal to array[1]. Elements 0 and 1 are now “dead”. `Subset[2]` is now chosen from `array[2]` through `array[array size()]`, and so on. My question is that if we're shrinking the array from which we're picking random numbers then probability of each number being picked `1/remaining_num_elements`. How does it stay equal for all the elements?