CODEWITHSUNDEEP
pythonalgorithmmathpermutationplaying-cards
Davo
Davo

Reputation: 566

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

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?

Upvotes: 7

Views: 539

Answers (1)

Peter de Rivaz
Peter de Rivaz

Reputation: 33509

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

Upvotes: 10

Related Questions