On Tue, 17 Feb 2009, Okasaki, C. DR EECS wrote:
The discussion of randomly permuting a list comes up every few years. Here’s
what I wrote last time (2005):
... How about putting it on the Wiki?___
Haskell-Cafe mailing list
The discussion of randomly permuting a list comes up every few years.
Here's
what I wrote last time (2005):
Clearly, you can do a perfect shuffle in O(N) time using mutable
arrays,
using the standard imperative algorithm. You can also do it in O(N)
expected time using *immutable* arrays, using
Heinrich Apfelmus wrote:
Alberto Ruiz wrote:
How about using random doubles?
randomPerm xs = fmap (map snd . sort . flip zip xs) rs
where rs = fmap (randoms . mkStdGen) randomIO :: IO [Double]
Interesting idea. The chance of duplicates should be negligible now, but
that's because we're
Paul Johnson p...@cogito.org.uk writes:
See http://okmij.org/ftp/Haskell/perfect-shuffle.txt
I should have read that first time round!
--
Jón Fairbairn jon.fairba...@cl.cam.ac.uk
http://www.chaos.org.uk/~jf/Stuff-I-dont-want.html (updated 2009-01-31)
Heinrich Apfelmus apfel...@quantentunnel.de writes:
The answer is a resounding yes and the main idea is that shuffling a
list is *essentially the same* as sorting a list; the minor difference
being that the former chooses a permutation at random while the latter
chooses a very particular
Jon Fairbairn wrote:
Heinrich Apfelmus writes:
The answer is a resounding yes and the main idea is that shuffling a
list is *essentially the same* as sorting a list; the minor difference
being that the former chooses a permutation at random while the latter
chooses a very particular
Heinrich Apfelmus wrote:
Jon Fairbairn wrote:
Heinrich Apfelmus writes:
The answer is a resounding yes and the main idea is that shuffling a
list is *essentially the same* as sorting a list; the minor difference
being that the former chooses a permutation at random while the latter
chooses a
On Sun, Feb 15, 2009 at 9:47 AM, Heinrich Apfelmus
apfel...@quantentunnel.de wrote:
It's fair, but may duplicate elements, i.e. it doesn't necessarily
create a permutation. For example, rs could be something like
rs = [5,3,3,3,2,4]
But our sort doesn't discard values when the keys are
Felipe Lessa wrote:
Heinrich Apfelmus wrote:
It's fair, but may duplicate elements, i.e. it doesn't necessarily
create a permutation. For example, rs could be something like
rs = [5,3,3,3,2,4]
But our sort doesn't discard values when the keys are the same. For example,
[1,2,3,4]
See http://okmij.org/ftp/Haskell/perfect-shuffle.txt
Paul.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
On Sat, 14 Feb 2009, Daniel Fischer wrote:
Am Samstag, 14. Februar 2009 16:37 schrieb Heinrich Apfelmus:
For the full exposition, see
http://apfelmus.nfshost.com/random-permutations.html
Excellent work, thanks.
Interesting read.
Btw. a further development of the PFP library is also
11 matches
Mail list logo
