G2A Many GEOs
SHARE
TWEET

Generalized Coupon Collector's problem

a guest Sep 8th, 2015 121 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #!/usr/bin/env python
  2.  
  3. ''' Expected numbers of coupons required to collect m sets of n coupons
  4.  
  5.    Using integral from p.23 of Ferrante & Saltalamacchia
  6.    http://mat.uab.cat/matmat/PDFv2014/v2014n02.pdf
  7.    Written by PM 2Ring 2015.09.05
  8. '''
  9.  
  10. from __future__ import print_function, division
  11.  
  12. import sys
  13. from mpmath import mp
  14.  
  15. #Set the precision
  16. #mp.dps = 30
  17.  
  18. zero = mp.mpf(0)
  19. one = mp.mpf(1)
  20.  
  21. #Factorial table
  22. factorials = []
  23.  
  24. def make_func(n, m):
  25.     fac = factorials[:m]
  26.     def func(t):
  27.         smt = sum(t**k / f for k,f in fac)
  28.         return one - (one - smt * mp.exp(-t)) ** n
  29.     return func
  30.  
  31. def main():
  32.     #n: number of coupons; mm: max number of sets
  33.     n = int(sys.argv[1]) if len(sys.argv) > 1 else 101
  34.     n = mp.mpf(n)
  35.     mm = int(sys.argv[2]) if len(sys.argv) > 2 else 10
  36.  
  37.     #Build factorial table
  38.     factorials.append((zero, one))
  39.     for i in range(1, mm):
  40.         ii = mp.mpf(i)
  41.         factorials.append((ii, ii * factorials[i-1][1]))
  42.  
  43.     print('Expected numbers of coupons required to collect m sets of %d coupons' % n)
  44.     print(' m: expected number')
  45.     for m in range(mm):
  46.         v = n * mp.quad(make_func(n, m), [zero, mp.inf])
  47.         print('%2d: %s' % (m, mp.nstr(v, 12)))
  48.  
  49.  
  50. if __name__ == '__main__':
  51.     main()
RAW Paste Data
Ledger Nano X - The secure hardware wallet
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top