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
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)