# 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!