3.42 RANDOM SAMPLING AND SHUFFLING 141 12. [M,E6] (Business web site)
3.42 RANDOM SAMPLING AND SHUFFLING 141 12. [M,E6] The gist of Algorithm P is that any permutation T can be uniquely written as a product of transpositions in the form T = (att) . . . (as3)(~2), where 1 2 a3 2 j for t 2 j > 1. Prove that there is also a unique representation of the form r = (b22)(b33). . . (btt), where 1 5 bj 2 j for 1 < j 5 t, and design an algorithm that computes the b s from the u s in O(t) steps. 13. [MB] (S. W. Golomb.) One of the most common ways to shuffle cards is to divide the deck into two parts as equal as possible, and to riffle them together. (See the discussion of card-playing etiquette in Hoyle s rules of card games; we read, A shuffle of this sort should be made about three times to mix the cards thoroughly. ) Consider adeckof2n-1 cardsXl,Xz, . . . . X2,-1; a perfect shuffle s divides this deck into X1, X2, . . . , X, and Xn+l, . . . , X2n--1, then perfectly interleaves them to obtain Xl, xn+1, x2, -%x+2, . . . , Xzn-l, X,. The cut operation c3 changes X1, X2, . . , Xzn-l into X3+1, . . . , X2n-1, Xl, ...I Xj. Show that by combining perfect shuffles and cuts, at most (2n -1)(2n -2) different arrangements of the deck are possible, if n > 1. F 14. [so] (Ole-Johan Dahl.) If Xk = k for 1 5 k 5 t at the start of Algorithm P, and if we terminate the algorithm when j reaches the value t -n, the sequence Xten+l, . . . , Xt is a random permutation of a random combination of n elements. Show how to simulate the effect of this procedure using only O(n) cells of memory. b 15. [Mz~] Devise a way to compute a random sample of n records from N, given N and n, based on the idea of hashing (Section 6.4). Your method should use O(n) storage locations and an average of O(n) units of time, and it should present the sample as a sorted set of integers 1 5 Xl < X2 < … < X, 5 N. 16. [.%I Discuss the problem of weighted sampling, where each subset of n elements is obtained with probability proportional to the product of the weights of the elements.