What's the best way to enumerate permutations of deck of cards?

Question

I'm looking to make a function that would assign a value to a specific shuffle of cards.

The function has to be bijective. The deck has 52 cards so there are 52! different shuffles, therefore the domain is the set of all permutations of 52 cards, and the codomain is integers from 1 to 52!.

What would be the best algorithm to do this fast and efficiently?

Pontefract

check out itertools.permutation – Musick

Answer 1

To encode a permutation to a value in pseudocode:

A = list of cards
value = 0
for i in range(52):
   cards_left = 52-i
   let pos = index of card i in A 
   delete A[pos]
   value = value * cards_left + pos

At the end, A will be an empty list, and value has a number representing the permutation.

To decode:

A = []
value is an input
for i in reversed(range(52)):
   cards_left = 52-i
   pos = value % cards_left
   value = value / cards_left
   Insert card i at index pos in A

At end, A should contain the original permutation.

Example Python code:

B=[3,2,0,1,4]

def encode(A):
    value = 0
    n = len(A)
    A = A[:] # Take a copy to avoid modifying original input array 
    for i in range(n):
       cards_left = n-i
       pos = A.index(i)
       del A[pos]
       value = value * cards_left + pos
    return value

def decode(value,n):
    A=[]
    for i in range(n-1,-1,-1):
       cards_left = n-i
       value,pos = divmod(value, cards_left)
       A.insert(pos,i)
    return A

v=encode(B)
print v
print decode(v,len(B))

Resistive

Looks like this is it :) will approve in a bit. – Pontefract

Nice solution! elegant and simple. – Musick

Can you elaborate a but how the decoding algo works? – Musick

It is like extracting digits from the number 123. Each time you take the bottom digit (modulo 10) and divide by 10. In this code, we have a different number of choices at each stage so the base gradually changes from 52 down to 1. You could also encode the value with a constant base (e.g. 52), but there would then be some values that would be illegal. – Resistive