Introduction to Algorithms (3rd Edition)

Chapter 5.3, Problem 7E :

(link: http://www.chegg.com/homework-help/Introduction-to-Algorithms-3rd-edition-chapter-5.3-problem-7E-solution-9780262033848)

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 mn, such that each m-subset is equally likely to be created. One way would be to set A[i]-1 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 130 Chapter 5 Probabilistic Analysis and Randomized Algorithms 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) 2 3 return D else S = RANDOM-SAMPLE(m-1, n-1) else s=su{i} 8 return S