randomly order a list

[Geoff Canyon]

Dar -- I hardly think you need my blessing, but I agree with your
definition of p(k). I ran some numbers through Wolfram Alpha, and it looks
like even for 100 item lists the probability of the first item being sorted
to the first spot is about 0.015, or 1.5 times what it should be if sorted
by random(the number of items).

Of course, that's not the overall probability that the list is mal-sorted.
That probability is much higher, and I'm not sure how to calculate it
(hanging my head in shame), but roughly:

Say you have a set of 100 items where each gets a unique random number to
sort by except for the first two, which both get 1. They *should* be able
to come out either A,B or B,A, but they can only come out A,B. Note that
this does not depend on what common number they get -- even if they both
got 100, then although both of them would be moved to a different spot in
the output, there should be two possible outcomes, but there is only one.
Hence the probability under this circumstance of having an improper shuffle
is 0.5.

Likewise, if three items had the same random number, there would be only
one possible outcome when there should be 3*2*1 = 6 possible outcomes, so
there is a 5/6 or roughly 0.83 probability of a bad shuffle. This goes up,
obviously, as the number of dupes increases. Further, there can be more
than one duplicated number. If two items have 99, and three others have 23,
then the probability of an improper shuffle is 1 - 1/2 * 1/6 = 1 - 1/12 =
about 0.92.

My failure comes in aggregating all the various possible sets of
duplicates. Of course, the goal is achieving success, not calculating
failure. I did the math (okay, Wolfram Alpha did the math) and using:

sort lines of myList by random(999999999) & random(999999999)

For a list 1 million lines long has a probability less than 1 in a million
of having even a *slightly* non-random order (within the bounds of the
random number generator). That seems good enough for me. For shorter lists
the concatenation would be unnecessary.

I commented on the feature request. I think this would be an excellent
application of the new language features once they are available.

gc