A better way to shuffle a list ~ fluffy

From: fluffy

Date: 2012-12-03 11:49 PM

The MPI documentation provides this code snippet for shuffling a list:

{lsort:{&list},v1,v2,{gt:{dice:100},50}}

This method, while easy to implement, is WRONG, WRONG, WRONG. It does

a terrible job of actually shuffling a list's elements. It will tend

to bias certain elements of the list to be in certain positions, and so

it won't actually be all that random.

A much better approach to shuffling a list's elements is like so:

{parse:pfx,{lsort:{parse:col,{&list},{dice:899,1,100}{&col}}},{midstr:{&pfx},4,-1}}

The way this works is that for every entry in the list, it prefixes it

with a random number from 100 to 999, then it shuffles the list based

on that number, and then strips that number off. It's a little silly,

but it will at least generate pretty good shufflings, as long as your

list has no more than 30 elements. (Once you exceed 30 elements, it

will start to bias the alphabetically-lower entries to higher up in the

list for reasons not worth getting into.)

Of course, if you want to improve the entropy, you can increase the

number of digits, for example:

{parse:pfx,{lsort:{parse:col,{&list},{dice:89999,1,10000}{&col}}},{midstr:{&pfx},6,-1}}

which will generate pretty good uniform selections for lists of up to

around 300 elements. (Essentially, adding two digits to the prefix will

add one digit's worth of uniform entropy.)

To see an example of this in action, look at me when I'm polka-dotted

or tie-dyed.