# Fast generation of permutations

Paul Rubin http
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:

def deals():
for i in xrange(13**5):
cards = [(i//p) % 13 for p in (1, 13, 169, 2197, 28561)]
yield cards

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

```