[Haskell-cafe] generalized shuffle
Manlio Perillo
manlio_perillo at libero.it
Mon Mar 23 19:35:53 EDT 2009
Hi.
I have implemented a generalized shuffle function, for the
random-shuffle package
http://hackage.haskell.org/cgi-bin/hackage-scripts/package/random-shuffle
I have not yet commited the change, before that I would like to receive
some feedbacks (especially by the original author of the shuffle
function, in Cc)
The new function is defined in this example:
http://hpaste.org/fastcgi/hpaste.fcgi/view?id=2808
Note that it make use of functions not exported by the
System.Random.Shuffle module.
I have generalized the original shuffle function in two ways:
1) It is now possible to obtain a random "sample" from a sequence,
by doing, as an example:
shuffles [1..10] [2, 3, 4, 2, 1]
Note that this is equivalent at taking the first 5 elements of the
full shuffled sequence, and the performance are pratically the same.
2) It is now possible to pass an infinite "r-sequence" to the shuffle
function, as an example:
shuffles [1..10] $ cycle [9, 8 .. 1]
The result is an infinite list, with elements cyclically extracted
from the "r-sequence".
When the "r-sequence" contains random numbers, we get an infinite
sequence containing all possible random "choices" of elements in the
original sequence.
Why I'm doing this?
The reason is that in a project I need to extract random elements
from a list (and I need to extract a lot of them), and using "normal"
methods [1] seems to be rather inefficient.
Using the `shuffles` function should be much more efficient, since it
uses a tree, and this tree is built only once.
[1] by normal method I mean: extract a random number, in the range
[0, n] (where n is the length of the sequence), and get the element
indexed by that number.
Indexing for a list if very expensive.
And it is not very fast, even using arrays (unless you use
non portable unsafeRead).
Thanks Manlio Perillo
More information about the Haskell-Cafe
mailing list