Fast generation of permutations
Wed Jan 25 16:39:24 EST 2006
Paul Rubin <http://phr.cx@NOSPAM.invalid> writes:
> Well, maybe not 24x. The exact number is more complicated. I'm still
> too sleepy to figure this out right now but may think about it later.
Turns out to be 7x, for reasons that are a bit mysterious.
Ignoring suits, think of the 5-card hand as a 5-digit number base 13.
There are 13**5 such numbers, but 13 of them are impossible as 5-card
deals (all 5 digits are the same, "5 of a kind"). That leaves
13**5-13 = 371280, which is 1/7th of C(52,5). Can someone give
a combinatorial explanation?
Generating the hands is simple:
for i in xrange(13**5):
cards = [(i//p) % 13 for p in (1, 13, 169, 2197, 28561)]
The funny numbers in that list are the first four powers of 13.
Flattening the generator with list() takes about 8 sec on my p3-750.
Unrolling the list comprehension and making tuples instead of lists,
cards = (i%13, (i//13)%13, (i//169)%13, (i//2197)%13, (i//28561)%13)
speeds it up to 5.6 seconds.
In categorizing the hands from this generator, you have to:
- discard the hands that are 5-of-a-kind (there are 13 of them)
- in hands where all 5 numbers are distinct, consider whether
the hand might be a flush (probability is 1 in 256).
More information about the Python-list