[Haskell-cafe] Linear Shuffle
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 Haskell's bulk array operations. 1. Start with a list of length N. If N 2, stop. 2. Pair each element with a random index in the range [1,2N] (or [0,2N-1]). 3. Use accum to create an array of size 2N, where slot I contains a list of all the elements paired with I. 4. Map the shuffle function recursively across the array to re-shuffle any slots that got more than one element. 5. Append all the slots together into the result list. If you leave out step 4, you get an algorithm that runs in O(N) worst-case time, rather than expected time, but you no longer have a perfect shuffle (although it might be good enough). Upping the size of the array from 2N to 3N or 4N will help reduce collisions, but will not entirely eliminate them. With step 4, you can imagine pathological cases where everything gets put in the same slot, but with a reasonable random number generator, it is vanishingly unlikely that you will have enough collisions to drive the cost higher than linear. Again, upping the size of the array from 2N to 3N or 4N makes this even more unlikely. -- Chris ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Linear shuffle
Marcin 'Qrczak' Kowalczyk wrote: Henning Thielemann [EMAIL PROTECTED] 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 [EMAIL PROTECTED] 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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Linear shuffle
Scott Turner wrote: Analogous to quicksort's bad behavior in the worst case, an invocation of 'partition' is not guaranteed to make any progress with the shuffling, because one of the output lists might receive all of the input items. It's worse than quicksort, because there's no guarantee that the algorithm will ever terminate. But this is actually optimal--there's no way to perfectly shuffle a list using a bounded number of coin flips, because n! doesn't divide any power of 2 for n=3. I posted this algorithm on comp.lang.functional a while ago: http://groups-beta.google.com/group/comp.lang.functional/browse_frm/thread/570615e64e3e4fc0 -- Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Linear shuffle
Hi, I want to implement linear list shuffle in Haskell (http://c2.com/cgi/wiki?LinearShuffle) and I invented code: 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? -- Gracjan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Linear shuffle
Gracjan Polak [EMAIL PROTECTED] 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. Then, given the index 'r' you could use 'splitAt r' to split the string, and join the first part to the tail of the second, prepending the head of the second. More precisely (I hope this is not a homework excercise :-): : (s1,s2) = splitAt r return (head s2 : s1 ++ tail s2) This reduces the three (four if you include length) traversals to one. -kzm -- If I haven't seen further, it is by standing in the footprints of giants ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Linear shuffle
Gracjan Polak wrote: This algorithm seems not effective, length, take, drop and (!!) are costly. Is there any better way to implement shuffle? Here is an algorithm known as a perfect-shuffle... I am not too sure of the efficiency compared to the example you gave, but it builds a tree to enable faster lookup. Keean module Lib.MetaSearch.Shuffle(shuffle) where import Random import Int import GHC.IOBase (unsafeInterleaveIO) data Tree a = Leaf a | Node !Int (Tree a) (Tree a) deriving Show buildTree :: [a] - Tree a buildTree = growLevel . (map Leaf) where growLevel :: [Tree a] - Tree a growLevel [node] = node growLevel l = growLevel (inner l) inner :: [Tree a] - [Tree a] inner [] = [] inner [e] = [e] inner (e1:e2:rest) = join e1 e2 : inner rest join :: Tree a - Tree a - Tree a join l@(Leaf _) r@(Leaf _) = Node 2 l r join l@(Node i _ _) r@(Leaf _) = Node (i+1) l r join l@(Leaf _) r@(Node i _ _) = Node (i+1) l r join l@(Node i _ _) r@(Node j _ _) = Node (i+j) l r shuffle1 :: [a] - [Int] - [a] shuffle1 elements rseq = shuffle' (buildTree elements) rseq where shuffle' :: Tree a - [Int] - [a] shuffle' (Leaf e) [] = [e] shuffle' tree (r0:rs) = case extractTree r0 tree of (b0,bs) - b0 : shuffle' bs rs extractTree :: Int - Tree a - (a,Tree a) extractTree 0 (Node _ (Leaf e) r) = (e,r) extractTree 1 (Node 2 (Leaf l) (Leaf r)) = (r,Leaf l) extractTree n (Node c (Leaf l) r) = case extractTree (n-1) r of (e,r') - (e,Node (c-1) (Leaf l) r') extractTree n (Node c l (Leaf e)) | n+1 == c = (e,l) extractTree n (Node c l@(Node c1 _ _) r) | n c1 = case extractTree n l of (e,l') - (e,Node (c-1) l' r) | otherwise = case extractTree (n-c1) r of (e,r') - (e,Node (c-1) l r') randList :: Int - IO [Int] randList 1 = return [] randList n = do a0 - getStdRandom $ randomR (0,n-1) as - unsafeInterleaveIO $ randList (n-1) return (a0:as) shuffle :: [a] - IO [a] shuffle s = do a - randList $ length s return $ shuffle1 s a ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Linear shuffle
Tomasz Zielonka [EMAIL PROTECTED] 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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Linear shuffle
On Fri, Jan 14, 2005 at 10:17:27AM +0100, Ketil Malde wrote: Tomasz Zielonka [EMAIL PROTECTED] 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. Perhaps I don't know this particular algorithm, but you can shuffle the array with linear number of swaps. No need to shift elements. Best regards, Tomasz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Linear shuffle
On Fri, 14 Jan 2005, Gracjan Polak wrote: I want to implement linear list shuffle in Haskell (http://c2.com/cgi/wiki?LinearShuffle) and I invented code: 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? Is it a good idea to use IO monad for this plain computation? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Linear shuffle
Please see: http://okmij.org/ftp/Haskell/perfect-shuffle.txt For an explanation of the algorithm. Keean. Ketil Malde wrote: Tomasz Zielonka [EMAIL PROTECTED] 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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Linear shuffle
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? Oleg wrote a great article on implementing the perfect shuffle. with some sample code. http://okmij.org/ftp/Haskell/misc.html#perfect-shuffle -- John Meacham - repetae.netjohn ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Linear shuffle
Tomasz Zielonka [EMAIL PROTECTED] 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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Linear shuffle
Keean Schupke [EMAIL PROTECTED] 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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Linear shuffle
Henning Thielemann wrote: Is it a good idea to use IO monad for this plain computation? It is needed as random number supply. -- Gracjan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Linear shuffle
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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Linear shuffle
Am Freitag, 14. Januar 2005 09:50 schrieb Ketil Malde: Gracjan Polak [EMAIL PROTECTED] 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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Linear shuffle
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) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Linear shuffle
Henning Thielemann [EMAIL PROTECTED] writes: 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. I think it doesn't guarantee equal probabilities of all permutations. -- __( Marcin Kowalczyk \__/ [EMAIL PROTECTED] ^^ http://qrnik.knm.org.pl/~qrczak/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Linear shuffle
Gracjan Polak [EMAIL PROTECTED] wrote: 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? Also, note that, in a lazy language, the algorithm's complexity will be dependent on the number of cards drawn from the deck, are possibly sub-linear in the number of cards in the deck. John ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
