|
Re^2: Functional shuffle
by rg0now (Chaplain) on Apr 02, 2005 at 16:08 UTC
|
Isn't it the case that random number generators do not entirely fit into the "pure functional" programming paradigm? I seem to recall reading somewhere that obtaining random numbers in Haskell involves the use of Monads, which is a kind of stretching of the concept of pure functional programming (maybe this is why I have never been able to really understand Monads?)...
This leads me to think that pure functional progamming is not the best way to attack the list shuffle problem...
| [reply] |
|
|
Indeed a "functional shuffle" is a contradiction in terms. In functional programming, if you give a function the same inputs you must get the same outputs. Rand is resetting a seed somewhere, which is a disallowed side-effect in a pure functional program. However, one could define a shuffle that took a list of random numbers from some outside source as an input. The paper referenced by the OP does this.
| [reply] |
|
|
You may very well be right. I did notice that in the article that Roy Johnson linked on the Haskell implementation the author spent longer than I would have expected on the discussion of the random numbers, which gave me the impression that the generation of random numbers has a conceptually different place, or different standing if you will, in the Haskell world than I'm used to from other programming languages.
But to be honest, I barely understand what this requirement that the shuffle be "functional" is, as is probably plainly obvious from my various stabs at it.
| [reply] |
Re^2: Functional shuffle
by tall_man (Parson) on Apr 02, 2005 at 16:31 UTC
|
Sort-based shuffles like this are not good shuffles. You do not get all N! permutations with equal probability. The Fisher-Yates shuffle can do it; this one does not. The discussion under When the Best Solution Isn't and under other recent shuffle threads (like Is this a fair shuffle?) explains why. | [reply] |
|
|
I agree that the sort-based shuffles discussed in When the Best Solution Isn't are fundamentally wrong, but this is one is qualitatively different; it doesn't work by tinkering with the sort function, but rather by assigning randomly numbered indexes to the elements of the array, and then sorting the array according to these indexes. The number of possible rank orderings of N randomly chosen real numbers r1,...,rN in the unit interval is N!.
The objection to this shuffle, I suspect, is not on the grounds of correctness but rather on the grounds of efficiency.
Also, whether this meets Roy Johnson's original requirement that the shuffle be in a "functional" vein (whatever that means) is highly dubious.
| [reply] |
|
|
I'm basing my objection to the sort-based shuffle on this note in the paper that Roy Johnson referenced:
Furthermore, if we have a sequence of N elements and associate with
each element a key -- a random number uniformly distributed within 0,
M-1 (where N!>M>=N), we have the configurational space of size M^N
(i.e., M^N ways to key the sequence). There are N! possible
permutations of the sequence. Alas, for N>2 and M<N!, M^N is not
evenly divisible by N!. Therefore, certain permutations are bound to
be a bit more likely than the others.
I would further argue that even when M (the period of the psuedo-random number generator) is larger than N, M^N is still not divisible by N! in general. The Fisher-Yates shuffle applies decreasing probabilities as it moves down the deck; the sorting shuffle uses uniform ones. That is the key difference.
I believe the discussion under A bad shuffle is also applicable.
| [reply] |
|
|
|
|
|
|
|
|
|
|
|
Did you compare the code above to the faulty code in your link? The code above is indeed a fair shuffle. Sort-based shuffles that use rand in the comparison block are the ones that don't work. See Re: Is this a fair shuffle?.
| [reply] |