Guest User

Generalized Coupon Collector's problem

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

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×