Suppose we want to create a random sample of the set {1, 2, 3, . . . , n}, that is, an m-element subset S, where 0 ≤ m ≤ n, such that each m-subset is equally likely to be created. One way would be to set A[i] = i for i = 1, 2, 3, . . . , n, call RANDOMIZE-IN-PLACE (A), and then take just the first m array elements. This method would make n calls to the RANDOM procedure. If n is much larger than m, we can create a random sample with fewer calls to RANDOM. Show that the following recursive procedure returns a random m-subset S of {1, 2, 3, . . . , n}, in which each m-subset is equally likely, while making only m calls to RANDOM:

RANDOM-SAMPLE (m, n)

1. if m == 0

2. return ⌀

3. else S = RANDOM-SAMPLE (m – 1, n – 1)

4. i = RANDOM (1, n)

5. if i ∈ S

6. S = S ⋃ {n}

7. else S = S ⋃ {i}

8. return S