Unsorting(randomizing) a sequence

[Charles G Waldman]

 > [Christopher Browne]
 > > Is it so much work to come up with a half-reasonable card shuffling
 > > algorithm?

Apparently so, since so few of the solutions posted (including yours)
have biases:

 > >
 > > The one I've always seen cited as providing decent behaviour looks
 > > thus:
 > >
 > > for (i = 0; i > n; i++) {  /* surely intended "i < n" */
 > >    swap (item[i], item[random(n)]);
 > > }
 > 

I fed this to my statistics-tester.  You can see that you tend to
favor odd permutations when the list is of an odd length and even
permutations when the list is of an even length.  You're swapping too
much, in essence.  The bias in the sign of the generated permutations
becomes more marked as the list becomes longer.

Also, the variances seem to be higher for elements later in the list,
although I'm not sure if the results below are statisticall
significant.

What these numbers are is the result of scrambling the sequences
[0,1], [0,1,2], ..., [0,..7]
each 50000 times, and recording the signs (+1/-1) of the generated
permutations and the means and RMS variances of each sequence element.
See my previous posts in this thread for more...

Note also that if you have a permutation algorithm that tends to favor 
elements from a subgroup (e.g. even permutations) then repeated
applications of the algorithm won't help you at all.



#Chris Brown's method
def brown(seq):
    for i in range(len(seq)):
        j=random.randrange(0,len(seq))
        seq[i],seq[j]=seq[j],seq[i]

Testing <function brown at 81604f0>
len= 2
 mean values= [0.49874, 0.50126]
 rms= [0.499998412397, 0.499998412397]
 mean sign= 0.00252
len= 3
 mean values= [0.9641, 1.03796, 0.99794]
 rms= [0.792698675412, 0.839523101767, 0.81492070559]
 mean sign= -0.03528
len= 4
 mean values= [1.41586, 1.52312, 1.55922, 1.5018]
 rms= [1.07712601881, 1.11809904105, 1.15433660238, 1.11626016681]
 mean sign= 0.06644
len= 5
 mean values= [1.86166, 1.99346, 2.06626, 2.08022, 1.9984]
 rms= [1.36447867129, 1.38496831314, 1.43166672532, 1.46173347489,
1.41552726572]
 mean sign= -0.07372
len= 6
 mean values= [2.31702, 2.43602, 2.56682, 2.59322, 2.58368, 2.50324]
 rms= [1.65208907738, 1.65539921457, 1.70093359294, 1.74600974556,
1.76338244791, 1.70917216874]
 mean sign= 0.0886
len= 7
 mean values= [2.77782, 2.91118, 3.0239, 3.0912, 3.10874, 3.09468,
2.99248]
 rms= [1.94859335101, 1.92894038467, 1.9772022633, 2.01373348783,
2.05070612531, 2.06344268096, 1.99186933547]
 mean sign= -0.09652
len= 8
 mean values= [3.2336, 3.37306, 3.46918, 3.57226, 3.6168, 3.63026,
3.6131, 3.49174]
 rms= [2.23409736583, 2.21326144782, 2.23776900676, 2.28316852037,
2.32304062814, 2.3567503755, 2.35576068182, 2.2918751651]
 mean sign= 0.10684