Generando enteros aleatorios con probabilidades dadas

Question

Necesito generar una secuencia infinita de enteros aleatorios, con números en el rango [1..n]. Sin embargo, la probabilidad para cada número p_i se da con antelación, por lo que la distribución no es uniforme.

¿Hay una función de biblioteca para hacerlo en Haskell?

Answer 1

Sólo para ampliar la respuesta de dflemstr, puede crear una lista infinita de valores ponderados usando Control.Monad.Random así:

import Control.Monad.Random 
import System.Random 

weightedList :: RandomGen g => g -> [(a, Rational)] -> [a] 
weightedList gen weights = evalRand m gen 
    where m = sequence . repeat . fromList $ weights 

Y utilizar de esta manera:

> let values = weightedList (mkStdGen 123) [(1, 2), (2, 5), (3, 10)] 
> take 20 values 
[2,1,3,2,1,2,2,3,3,3,3,3,3,2,3,3,2,2,2,3] 

Esto no requiere la mónada IO, pero debe proporcionar el generador de números aleatorios que se usa para la transmisión.

Answer 2

Control.Monad.Random ofrece esta función en forma de fromList:: MonadRandom m => [(a, Rational)] -> m a

Se puede utilizar en el IO Mónada con:

import Control.Monad.Random 
-- ... 
someNums <- evalRandIO . sequence . repeat . fromList $ [(1, 0.3), (2, 0.2), (3, 0.5)] 
print $ take 200 someNums 

Hay otras maneras de ejecutar el Rand Mónada como se puede ver en ese paquete . Los pesos no tienen que sumar 1.

EDIT:Rand es aparentemente más perezoso de lo que pensaba, por lo replicateM n pueden ser reemplazados por sequence . repeat, como @shang sugeridos.

Answer 3

Como se ha señalado, existe una función en Control.Monad.Random, pero tiene una complejidad bastante baja. Aquí hay un código que por alguna coincidencia escribí esta mañana. Utiliza el hermoso algoritmo Alias.

module Data.Random.Distribution.NonUniform(randomsDist) where 
import Data.Array 
import Data.List 
import System.Random 

genTable :: (Num a, Ord a) => [a] -> (Array Int a, Array Int Int) 
genTable ps = 
    let n = length ps 
     n' = fromIntegral n 
     (small, large) = partition ((< 1) . snd) $ zip [0..] $ map (n' *) ps 
     loop ((l, pl):ls) ((g, pg):gs) probs aliases = 
      let prob = (l,pl) 
       alias = (l,g) 
       pg' = (pg + pl) - 1 
       gpg = (g, pg') 
      in if pg' < 1 then loop (gpg:ls) gs (prob:probs) (alias:aliases) 
          else loop ls (gpg:gs) (prob:probs) (alias:aliases) 
     loop ls gs probs aliases = loop' (ls ++ gs) probs aliases 
     loop' [] probs aliases = (array (0,n-1) probs, array (0,n-1) aliases) 
     loop' ((g,_):gs) probs aliases = loop' gs ((g,1):probs) ((g, -1):aliases) 
    in loop small large [] [] 

-- | Generate an infinite list of random values with the given distribution. 
-- The probabilities are scaled so they do not have to add up to one. 
-- 
-- Uses Vose's alias method for generating the values. 
-- For /n/ values this has O(/n/) setup complexity and O(1) complexity for each 
-- generated item. 
randomsDist :: (RandomGen g, Random r, Fractional r, Ord r) 
      => g       -- | random number generator 
      -> [(a, r)]     -- | list of values with the probabilities 
      -> [a] 
randomsDist g xps = 
    let (xs, ps) = unzip xps 
     n = length xps 
     axs = listArray (0, n-1) xs 
     s = sum ps 
     (probs, aliases) = genTable $ map (/ s) ps 
     (g', g'') = split g 
     is = randomRs (0, n-1) g' 
     rs = randoms g'' 
     ks = zipWith (\ i r -> if r <= probs!i then i else aliases!i) is rs 
    in map (axs!) ks