# 99 questions/Solutions/25

### From HaskellWiki

< 99 questions | Solutions(Difference between revisions)

Remi.berson (Talk | contribs) m (first solution used diff_select instead of rnd_select) |
|||

(5 intermediate revisions by 4 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 18: | Line 18: | ||

rest <- rnd_permu xs |
rest <- rnd_permu xs |
||

return $ let (ys,zs) = splitAt rand rest |
return $ let (ys,zs) = splitAt rand rest |
||

− | in ys++(x:zs) |
+ | 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 |
||

</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

permutations

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