Random Permutations

[Jacques Carette]

Pertinent to this thread (though perhaps overkill) is the work of Flajolet
et al on (fast) random generation of combinatorial structures for any
structure given as a context-free grammar, including Permutation.

In particular see
http://citeseer.nj.nec.com/flajolet93calculus.html
http://citeseer.nj.nec.com/flajolet95computer.html

There is a complete implementation of this in Maple as well as a partial
port to MuPAD.  The Maple version is available at
http://pauillac.inria.fr/algo/libraries/libraries.html.  Also worth a look
is the set of fully documented example applications (available in various
formats) at
http://pauillac.inria.fr/algo/libraries/autocomb/autocomb.html

A translation of the random generation parts of this work to Haskell would
not be too difficult, and might in fact be easier than the original,
although a full translation would require Template Haskell.  Translating the
automatic generation of the 'counting' functions would be very challenging
[as no one has, as far as I know, yet to create a workable, truly
statically-typed computer algebra system!]

Jacques