[Daniel Yoo]
There was a question about ways of generating permutations: is there an easy way to show that these two functions:
### def permuteRestricted(L): newlist = L[:] # shallow copy for i in range(len(L)): rand_i = randint(i, len(L)-1) newlist[i], newlist[rand_i] = newlist[rand_i], newlist[i] return newlist
def permuteUnrestricted(L): newlist = L[:] # shallow copy for i in range(len(L)): rand_i = randint(0, len(L)-1) rand_j = randint(0, len(L)-1) newlist[rand_j], newlist[rand_i] = newlist[rand_i], newlist[rand_j] return newlist ###
act differently? ...
By counting. Let N=len(L). Then in the first version, there are N! (N factorial) possible outcomes (on the first iteration thru the loop, rand_i can have any of N values; on the second iteration, any of N-1; and so on). In the second version, N**(2*N) (on the first iteration thru the loop, the pair (rand_i, rand_j) can take any of N**2 values; and likewise for all the other iterations). Since there are N! possible permutations, that the first version has N! possible outcomes means it's at least *possible* for each permutation to be equally likely (the counting argument alone can't prove it's fair, though -- it simply doesn't rule fairness out). But the second version can't possibly be fair unless N**(2*N) is a multiple of N!. That is, I think, what makes it so seductive: the second version *is* fair if N happens to be 1 or 2. People think about the small cases, and leap to the conclusion that it "must be" fair for larger N too. But for N==3, 6 (3!) does not divide 729 (3**6), so the second version necessarily favors some permutations. Note that "the usual" wrong algorithm for generating a random permutation is a bit simpler than permuteUnrestricted: def permuteUnrestricted_usual(L): newlist = L[:] # shallow copy for i in range(len(L)): rand_j = randint(0, len(L)-1) newlist[i], newlist[rand_j] = newlist[rand_j], newlist[i] return newlist The same kind of counting argument shows that it can't be fair for len(L)>2. An exact analysis is quite difficult! probability-is-full-of-surprises-ly y'rs - tim