Randomize eine Haskell Liste

Question

ich ein Haskell Programm schreiben wollen, das die Elemente in einer Liste „ramdomize“:

import System.Random (getStdGen, randomRIO) 
import Data.List (permutations) 

rndElem :: [a] -> IO a 
rndElem xs = do 
    index <- randomRIO (0, length xs - 2) 
    return $ xs !! index 

rndPermutation :: [a] -> IO [a] 
rndPermutation xs = rndElem . permutations $ xs 

jedoch läuft dies scheint nicht vollständig um die Liste randomisieren. Es wird nur zufällig jedes andere Element aus irgendeinem Grund, z. [1,2,3,4,5,6] ->[5,2,1,4,3,6]. Jeder Durchlauf dieses Algorithmus hält die ungeraden Indexelemente (2, 4, 6) an der gleichen Stelle. Gibt es irgendwelche logischen Fehler bei der Indexierung des obigen Algorithmus?

Answer 1

Versuchen Sie diesen Code ausführen:

import System.Random (getStdGen, randomRIO) 
import Data.List (permutations) 

rndElem :: [a] -> IO Int 
rndElem xs = do 
    index <- randomRIO (0, length xs - 7) 
    return index 

und dann die 7 auf eine 6 zu einem 5 und so weiter zu ändern.

Hoffentlich erklärt dies meine Frage über die '2', und vielleicht wird das Ihnen helfen herauszufinden, was der Code tut.

Answer 2

Ein ziemlich netter Algorithmus zur Randomisierung endlicher Listen ist der Fisher-Yates shuffle, aka Knuth shuffle. Hier ist die Haskell version von Rosetta Code:

import System.Random 
import Data.List 
import Control.Monad 

mkRands = mapM (randomRIO.(,)0). enumFromTo 1. pred 

replaceAt :: Int -> a -> [a] -> [a] 
replaceAt i c l = let (a,b) = splitAt i l in a++c:(drop 1 b) 

swapElems :: (Int, Int) -> [a] -> [a] 
swapElems (i,j) xs | i==j = xs 
        | otherwise = replaceAt j (xs!!i) $ replaceAt i (xs!!j) xs 

knuthShuffle :: [a] -> IO [a] 
knuthShuffle xs = 
    liftM (foldr swapElems xs. zip [1..]) (mkRands (length xs))