in reply to Re: Random Derangement Of An Array in thread Random Derangement Of An Array
I'm skeptical about this one. It's nice, but it can only give factorial(n1) possible outputs, since that is the number of choices made in the algorithm. But there are many more derangements than that  the number is essentially factorial(n)/e, which is larger if n>2. So I don't think it gets the entire range of derangements.
For instance, I think one that it wouldn't be able to get is: (4,3,2,1). In the last step, you must swap the 4 into its final position, so the 4 would have to be swapped with the 1 in the first position. But the 1 would definitely no longer be in the first position at that time.
Re^3: Random Derangement Of An Array by jethro (Monsignor) on Jul 06, 2008 at 12:46 UTC 
Excellent example. So that algorithm is sadly lacking, and my proof has a hole as well. That happens when you try to proove something in your head instead of really doing the math.
 [reply] 
