• API
• FAQ
• Tools
• Archive
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) if len(sys.argv) > 1 else 101
34.     n = mp.mpf(n)
35.     mm = int(sys.argv) 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]))
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.
Top