Welcome, guest | Sign In | My Account | Store | Cart

Calculates the probability that, when making k random selections out of n possibilities, at least two of the selections are the same. See: http://en.wikipedia.org/wiki/Birthday_problem

What is the probability that (at least) two people in a class of 30 share their birthday?

``````>>> collide(30,365)
0.7063162427192688
``````

What is the probability that ORA_HASH generates the same hash when hashing 25000 values?

``````>>> collide(25000,int(4.3e9))
0.07009388771353198
``````
Python, 15 lines
 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15``` ```import itertools def alldifferent(k,n): '''The probability that k random selections from n possibilities are all different.''' assert(k<=n) nums = xrange(n,n-k,-1) dens = itertools.repeat(n) fracs = itertools.imap(lambda x,y: float(x)/y, nums,dens) return reduce(float.__mul__, fracs) def collide(k,n): '''The probability that, in k random selections from n possibilities, at least two selections collide.''' return 1 - alldifferent(k,n) ``` Created by Sander Evers on Wed, 19 Dec 2012 (MIT)