生成給定概率的隨機整數

Question

我需要生成一個隨機整數的無限流，數字在範圍[1..n]。然而，預先給出每個數字p_i的概率，因此分佈不均勻。

在Haskell中是否有庫函數？

Answer 1

只是對dflemstr的答案擴大，您可以使用Control.Monad.Random這樣創造的加權值的無窮列表：

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 

而且使用這樣的：

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

這並不需要IO monad，但您需要提供用於流的隨機數生成器。

Answer 2

Control.Monad.Random提供在fromList:: MonadRandom m => [(a, Rational)] -> m a

形式此功能可以在IO單子與使用它：

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

有運行Rand單子的其他方式，你可以在包看。權重不必加起來1

編輯：Rand比我想象的明顯懶惰，所以replicateM n可以通過sequence . repeat取代，如@shang建議。

Answer 3

正如人們指出Control.Monad.Random中有一個函數，但它的複雜度相當差。下面是我今天上午寫的一些巧合的代碼。它使用美麗的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