Tạo các số nguyên ngẫu nhiên với xác suất đã cho

Question

Tôi cần tạo một luồng vô hạn các số nguyên ngẫu nhiên, với các số nằm trong phạm vi [1..n]. Tuy nhiên xác suất cho mỗi số p_i được đưa ra trước, do đó sự phân bố không đồng đều.

Có chức năng thư viện nào để thực hiện trong Haskell không?

Answer 1

Chỉ cần mở rộng về câu trả lời dflemstr, bạn có thể tạo ra một danh sách vô hạn các giá trị gia quyền sử dụng Control.Monad.Random như thế này:

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 

Và sử dụng nó như thế này:

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

này không yêu cầu đơn nguyên IO, nhưng bạn cần phải cung cấp trình tạo số ngẫu nhiên được sử dụng cho luồng.

Answer 2

Control.Monad.Random cung cấp chức năng này trong hình thức fromList:: MonadRandom m => [(a, Rational)] -> m a

Bạn có thể sử dụng nó trong các IO Monad với:

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

Có nhiều cách khác chạy Rand Monad như bạn có thể nhìn thấy trong gói phần mềm đó . Trọng lượng không cần phải thêm lên đến 1.

EDIT:Rand là rõ ràng lazier hơn tôi nghĩ, vì vậy replicateM n có thể được thay thế bằng sequence . repeat, như @shang gợi ý.

Answer 3

Vì mọi người đã chỉ ra rằng có một hàm trong Control.Monad.Random, nhưng nó có độ phức tạp khá kém. Đây là một số mã mà tôi đã viết một số sự trùng hợp sáng nay. Nó sử dụng thuật toán Alias ​​đẹp.

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