दिए गए संभाव्यताओं के साथ यादृच्छिक पूर्णांक उत्पन्न करना

Question

मुझे सीमाओं में होने वाली संख्याओं के साथ यादृच्छिक पूर्णांक की एक अनंत स्ट्रीम उत्पन्न करने की आवश्यकता है [1..n]। हालांकि प्रत्येक नंबर p_i के लिए संभावना पहले से दी जाती है, इसलिए वितरण एक समान नहीं है।

क्या हास्केल में ऐसा करने के लिए कोई लाइब्रेरी फ़ंक्शन है?

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] 

यह की आवश्यकता नहीं है आईओ मोनैड, लेकिन आपको यादृच्छिक संख्या जेनरेटर प्रदान करना होगा जो स्ट्रीम के लिए उपयोग किया जाता है।

Answer 2

Control.Monad.RandomfromList:: 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 इकाई चलाने का अन्य तरीकों से आपको लगता है कि पैकेज में देख सकते हैं कर रहे हैं । इसलिए replicateM n, sequence . repeat द्वारा बदला जा सकता है के रूप में @shang सुझावRand जाहिरा तौर पर lazier से मैंने सोचा है,: वजन करने के लिए 1.

संपादित करें जोड़ने के लिए नहीं है।

Answer 3

जैसा कि लोगों ने इंगित किया है कि Control.Monad.Random में कोई फ़ंक्शन है, लेकिन इसमें बहुत कम जटिलता है। यहां कुछ कोड है जो मैंने आज सुबह कुछ संयोग से लिखा था। यह सुंदर एलियास एल्गोरिदम का उपयोग करता है।

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