unsort, my first useful OCaml program

[Dave Long]

> (* I wonder if there's an efficient way to randomly shuffle a list
>    without mutation? *)

What primitives do we have?  Each permutation of the list is a random  
shuffle, so we should be able to pick one by taking a random number mod  
the factorial of the length of the list.  This code:

>     for i = Array.length result - 1 downto 0 do
>         let other = Random.int (i + 1) and tmp = result.(i) in
>         result.(i) <- result.(other) ; result.(other) <- tmp
>     done; Array.to_list result

is essentially generating a list of swaps, where the first swap can be any  
of Array.length, the next of Array.length - 1, usw.  (substitute "location  
of maximum" for Random, and one has a selection sort[0] instead of a  
shuffle[1])  This list of swaps can also be viewed as the digits of a  
number written in a varying-base system.

In APL[2], the "base encode" (drawn here as tau, should be a tack)  
primitive produces the radix representation without mutation:

  RR:1+(Φιω)τ_1+ι!ω

in python[3] (if one isn't worried about lexicographical order, and wishes  
to select a single permutation), a simple recursive equivalent is:

  rr = lambda n,k: (n > 1) and [k%n] + rr(n-1,k/n) or [0]

The trick here seems to be getting to the direct representation (list of  
indices into the original array instead of list of swaps in the swapped  
subarrays, which requires folding over all the swaps), efficiently and  
without mutation -- although if one is using the shuffle to get mp3s from  
disk, generating n lists using O(n**2) integer increments (see "dfr" in  
[1,2]) is unlikely to be expensive.

-Dave

[0] http://en.literateprograms.org/Selection_sort_(Python%2C_arrays)
[1] a sort is one given shuffle, but there are also others which are not  
so random -- for instance, a common application seems to be allowing users  
to shuffle columns in a database without any physical rearrangement by  
keeping track of which logical shuffle of the physical data they want.  In  
the same domain, one might wish to reshuffle a naive sort so that APR AUG  
DEC FEB JAN JUL JUN MAR MAY NOV OCT SEP come out in calendar order.
[2] Iverson, "Notation as a Tool of Thought", 1979 Turing award lecture
     http://elliscave.com/APL_J/tool.pdf
[3] http://en.literateprograms.org/Kth_permutation_(Python%2C_functional)

:: :: ::

> if memory serves it involved a multiplication deriving from the current  
> index somehow so that the fractional probabilities of picking an element  
> would sum up to 1.0 for all elements by the end of the shuffle(?).

I think that's the "pick a random element in a single pass" -- the  
equivalent of Random.int (i+1) when one doesn't know i.  It's also  
interesting to try without mutation.