Difference between revisions of "99 questions/Solutions/25"
< 99 questions | Solutions
Jump to navigation
Jump to search
Remi.berson (talk | contribs) 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 |
+ | rnd_permu :: [a] -> IO [a] |
+ | rnd_permu xs = rnd_select xs (length xs) |
||
</haskell> |
</haskell> |
||
− | Uses the solution |
+ | 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 28: | ||
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