<div class="gmail_quote"><br><br>I've abeen recommended on good authority(my son, a Cambridge Pure maths graduate, and Perl/Haskell expert) , and backed by a Google search that Fisher-Yates shuffle is the one to use, as it produces total unbiased results with every combination equally possible. <div>
As with most things with computers,don't reinvent the eheel, it's almost certainly been done before by someone brighter that you, Fisher,Yates. & Knuth!</div><div>--</div><div>Andrew Smith B.Sc(Hons),MBA</div>
<div>Edinburgh,Scotland<div><div></div><div class="h5"><br><br><div class="gmail_quote">On 27 August 2010 21:02, Gaius Hammond <span dir="ltr"><<a href="mailto:gaius@gaius.org.uk" target="_blank">gaius@gaius.org.uk</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Hi all,<br>
<br>
<br>
<br>
I am trying to randomly reorder a list (e.g. shuffle a deck of cards) . My initial approach is to treat it as an array, generate a list of unique random numbers between 0 and n - 1, then use those numbers as new indexes. I am using a function to generate random numbers in the State monad as follows:<br>
<br>
<br>
<br>
randInt∷ Int → State StdGen Int<br>
randInt x = do g ← get<br>
(v,g') ← return $ randomR (0, x) g<br>
put g'<br>
return v<br>
<br>
<br>
<br>
This is pretty much straight from the documentation. My function for the new indexes is:<br>
<br>
<br>
<br>
-- return a list of numbers 0 to x-1 in random order randIndex∷ Int → StdGen → ([Int], StdGen)<br>
randIndex x = runState $ do<br>
let randIndex' acc r<br>
| (length acc ≡ x) = acc<br>
| (r `elem` acc) ∨ (r ≡ (−1)) = do<br>
r' ← randInt (x − 1)<br>
randIndex' acc r'<br>
| otherwise = do<br>
r' ← randInt (x − 1)<br>
randIndex' r:acc r'<br>
in<br>
randIndex' [] (−1)<br>
<br>
<br>
<br>
This fails to compile on<br>
<br>
<br>
<br>
<br>
Couldn't match expected type `[a]'<br>
against inferred type `State StdGen b'<br>
In a stmt of a 'do' expression: r' <- randInt (x - 1)<br>
In the expression:<br>
do { r' <- randInt (x - 1);<br>
randIndex' acc r' }<br>
<br>
<br>
<br>
<br>
I can see what's happening here - it's treating randIndex' as the second argument to randInt instead of invisibly putting the State in there. Or am I going about this completely the wrong way?<br>
<br>
<br>
Thanks,<br>
<br>
<br>
<br>
G<br>
<br>
<br>
<br>
<br>
_______________________________________________<br>
Beginners mailing list<br>
<a href="mailto:Beginners@haskell.org" target="_blank">Beginners@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/beginners" target="_blank">http://www.haskell.org/mailman/listinfo/beginners</a><br>
</blockquote></div><br></div></div></div>
</div><br>