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