SHARE
TWEET

Generalized Coupon Collector's problem

a guest Sep 8th, 2015 111 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
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