Tomasz Zielonka writes:

On Fri, Jan 14, 2005 at 09:17:41AM +0100, Gracjan Polak wrote:

...

This algorithm seems not effective, length, take, drop and (!!) are costly. Is there any better way to implement shuffle?

You can use mutable arrays (modules Data.Array.MArray, Data.Array.IO).

But is that better, really? IIUC, you will now need to shift the first part of the string to the right, so it's still a linear operation for each shuffle. -kzm -- If I haven't seen further, it is by standing in the footprints of giants

Tomasz Zielonka writes:

...

But is that better, really? IIUC, you will now need to shift the first part of the string to the right, so it's still a linear operation for each shuffle.

Perhaps I don't know this particular algorithm, but you can shuffle the array with linear number of swaps. No need to shift elements.

Right - this implementation picked an arbitrary element, placed it in front, and repeated, if I understood it correctly. Slightly different from moving each element to a random position (e.g. after k shuffles, elements (k+1..n) will be in the original order), but perhaps this too can be easily emulated with an array-based (direct) shuffle? -kzm -- If I haven't seen further, it is by standing in the footprints of giants

Keean Schupke writes:

Please see: http://okmij.org/ftp/Haskell/perfect-shuffle.txt For an explanation of the algorithm.

Right. I was commenting based on the source posted by Gracjan. (And http://c2.com/cgi/wiki?LinearShuffle contains a variety of shuffling algorithms). -kzm -- If I haven't seen further, it is by standing in the footprints of giants

Am Freitag, 14. Januar 2005 09:50 schrieb Ketil Malde:

Gracjan Polak writes:

...

shuffle :: [a] -> IO [a] shuffle [] = return [] shuffle x = do r <- randomRIO (0::Int,length x - 1) s <- shuffle (take r x ++ drop (r+1) x) return ((x!!r) : s)

This algorithm seems not effective, length, take, drop and (!!) are costly. Is there any better way to implement shuffle?

The length seems to me to be constant, so you could presumably calculate it once, and pass it as a parameter.

Whether the length is constant depends on how you interpret this statement, passing it as a parameter is absolutely the thing to do, say shuffle :: [a] -> IO [a] shuffle as = do let len = length as lenShuffle as len lenShuffle :: [a] -> Int -> IO [a] lenShuffle _ 0 = return [] lenShuffle as n = do r <- randomRIO (0,n-1) let (xs, h:ys) = splitAt r as s <- lenShuffle (xs++ys) (n-1) return (h:s)

This reduces the three (four if you include length) traversals to one.

and apparently is of linear behaviour. BTW, if splitAt were implemented as stated in the report, it wouldn't be any better than using take and drop, even as is, it saves only about 25% of the work. The real villains in the original code are the repeated evaluation of length and (!!), both leading to O(n^2) complexity (I think, I didn't properly analyze it).

-kzm all the best, Daniel

On Fri, 14 Jan 2005, Scott Turner wrote:

The shuffling algorithms mentioned so far are comparable to insertion/selection sort. I had come up with a shuffler that relates to quicksort, in that it partitions the input randomly into lists and works recursively from there. It looks efficient and works out well in Haskell.

I did some shuffling based on mergesort, that is a list is randomly split (unzipped) into two lists and the parts are concatenated afterwards. You must repeat this some times. It even works for infinite lists. It doesn't need IO.

randomPermute :: RandomGen g => [a] -> g -> ([a],g) randomPermute x g0 = let (choices,g1) = runState (mapM (const (State (randomR (False,True)))) x) g0 xc = zip x choices in (map fst (filter snd xc ++ filter (not . snd) xc), g1)

Marcin 'Qrczak' Kowalczyk wrote:

Henning Thielemann writes:

...

I did some shuffling based on mergesort [...]

I think it doesn't guarantee equal probabilities of all permutations.

It doesn't (proof: it has a bounded runtime, which can't be true of a perfect shuffling algorithm based on coin flips). But it looks pretty good. I think that iterating this algorithm n times is equivalent to assigning a random n-bit number to each list element and sorting, which is equivalent to Chris Okasaki's approach with one iteration and an array of size 2^n. Henning Thielemann writes:

It even works for infinite lists.

In the sense that it doesn't diverge if you evaluate any finite prefix of the list, yes. In the sense that it does a good job of shuffling the list, no. -- Ben

Henning Thielemann wrote:

Is it a good idea to use IO monad for this plain computation?

It is needed as random number supply. -- Gracjan

John Meacham wrote:

Oleg wrote a great article on implementing the perfect shuffle. with some sample code.

http://okmij.org/ftp/Haskell/misc.html#perfect-shuffle

Thats the kind of answer I was hoping to get :) Thanks. shuffle could be useful in standard library. At least Python has it. I was translating some small Python program, the hardest part was the missing shuffle function. What do you think? -- Gracjan