Introduction to Algorithms CLRS Book Exercise 5.3-7.

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 0 ; 3 else S = RANDOM-SAMPLE (m - 1 , n - 1) 4 i = RANDOM (1, n) 5 if i belongs to S 6 S = S U {n} 7 else S = S U {i} 8 return S