Skip to content

Instantly share code, notes, and snippets.

@sphynx
Created March 26, 2015 21:38
Show Gist options
  • Save sphynx/4aab07d3e8417f790ea0 to your computer and use it in GitHub Desktop.
Save sphynx/4aab07d3e8417f790ea0 to your computer and use it in GitHub Desktop.
Solver for probabilistic coupons problem
import Data.Ratio
main :: IO ()
main = print $ result 5
result :: Integer -> Rational
result size = abs $ sum
[ fromIntegral mult * infTailSum size d
| (mult, d) <- coeffs size
]
coeffs :: Integer -> [(Integer, Rational)]
coeffs size =
[ ( ((-1) ^ i) * choose (size - 1) i, i % size)
| i <- [1 .. size - 1]
]
infTailSum :: Integer -> Rational -> Rational
infTailSum size d = infiniteSum - partialSum where
infiniteSum = 1 / ((1 - d) ^ 2)
partialSum = sum [ (i%1) * d ^ (i - 1) | i <- [1 .. size - 1]]
choose :: Integer -> Integer -> Integer
choose n k = fact n `div` (fact (n - k) * fact k)
fact :: Integer -> Integer
fact n = product [1 .. n]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment