Generazione di numeri interi casuali con probabilità date

Question

Ho bisogno di generare un flusso infinito di numeri interi casuali, con numeri compresi nell'intervallo [1..n]. Tuttavia la probabilità per ogni numero p_i è data in anticipo, quindi la distribuzione non è uniforme.

Esiste una funzione di libreria per farlo in Haskell?

Answer 1

Giusto per ampliare la risposta di dflemstr, è possibile creare un elenco infinito di valori ponderati usando Control.Monad.Random come questo:

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 

e usarlo in questo modo:

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

Questo non richiede la monade IO, ma è necessario fornire il generatore di numeri casuali utilizzato per lo streaming.

Answer 2

Control.Monad.Random offre questa funzione in forma di fromList:: MonadRandom m => [(a, Rational)] -> m a

Si può usare nel IO Monade con:

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

Ci sono altri modi di gestione del Rand Monade, come si può vedere in questo pacchetto . I pesi non devono aggiungere fino a 1.

EDIT:Rand è apparentemente più pigri di quanto pensassi, così replicateM n possono essere sostituiti da sequence . repeat, come @shang suggerito.

Answer 3

Come le persone hanno sottolineato, esiste una funzione in Control.Monad.Random, ma ha una complessità piuttosto scarsa. Ecco un codice che ho scritto per una coincidenza stamattina. Usa il bellissimo 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