Personal tools

99 questions/Solutions/25

From HaskellWiki

< 99 questions | Solutions(Difference between revisions)
Jump to: navigation, search
m (first solution used diff_select instead of rnd_select)
 
(4 intermediate revisions by 3 users not shown)
Line 2: Line 2:
   
 
<haskell>
 
<haskell>
rnd_permu xs = diff_select' (length xs) xs
+
rnd_permu :: [a] -> IO [a]
  +
rnd_permu xs = rnd_select xs (length xs)
 
</haskell>
 
</haskell>
   
Uses the solution for the previous problem. Choosing N distinct elements from a list of length N will yield a permutation.
+
Uses the solution of problem 23 (rnd_select). Choosing N distinct elements from a list of length N will yield a permutation.
   
 
Or we can generate the permutation recursively:
 
Or we can generate the permutation recursively:
Line 27: Line 27:
 
return $ (xs!!rand):rest
 
return $ (xs!!rand):rest
 
</haskell>
 
</haskell>
  +
  +
Or we can use the <hask>permutations</hask> function from <hask>Data.List</hask>:
  +
<haskell>
  +
import System.Random (getStdGen, randomRIO)
  +
import Data.List (permutations)
  +
  +
rndElem :: [a] -> IO a
  +
rndElem xs = do
  +
index <- randomRIO (0, length xs - 1)
  +
return $ xs !! index
  +
  +
rndPermutation :: [a] -> IO [a]
  +
rndPermutation xs = rndElem . permutations $ xs
  +
</haskell>
  +
  +
WARNING: this may choke long lists
  +
  +
  +
[[Category:Programming exercise spoilers]]

Latest revision as of 13:08, 10 May 2014

Generate a random permutation of the elements of a list.

rnd_permu :: [a] -> IO [a]
rnd_permu xs = rnd_select xs (length xs)

Uses the solution of problem 23 (rnd_select). Choosing N distinct elements from a list of length N will yield a permutation.

Or we can generate the permutation recursively:

import System.Random (randomRIO)
 
rnd_permu :: [a] -> IO [a]
rnd_permu []     = return []
rnd_permu (x:xs) = do
    rand <- randomRIO (0, (length xs))
    rest <- rnd_permu xs
    return $ let (ys,zs) = splitAt rand rest
             in ys++(x:zs)
 
rnd_permu' [] = return []
rnd_permu' xs = do
    rand <- randomRIO (0, (length xs)-1)
    rest <- let (ys,(_:zs)) = splitAt rand xs
            in rnd_permu' $ ys ++ zs
    return $ (xs!!rand):rest
Or we can use the
permutations
function from
Data.List
:
import System.Random (getStdGen, randomRIO)
import Data.List (permutations)
 
rndElem :: [a] -> IO a
rndElem xs = do
  index <- randomRIO (0, length xs - 1)
  return $ xs !! index
 
rndPermutation :: [a] -> IO [a]
rndPermutation xs = rndElem . permutations $ xs

WARNING: this may choke long lists