More permutation madness [Cryptonomicon]
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? I tried to prove this difference by brute force: the attached program generates the whole space of permutations, given these two methods. I have to apologize for the code's uglyness and sluggishness, and if anyone can simplify or optimize it, I'd be very happy. I hope this helps!
[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 N1; 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! probabilityisfullofsurprisesly y'rs  tim
participants (2)

Daniel Yoo

Tim Peters