7

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?

Davo
  • 526
  • 3
  • 19

1 Answers1

10

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))
Peter de Rivaz
  • 33,126
  • 4
  • 46
  • 75
  • Looks like this is it :) will approve in a bit. – Davo Jan 05 '18 at 12:29
  • 1
    Nice solution! elegant and simple. – Chen A. Jan 05 '18 at 12:30
  • Can you elaborate a but how the decoding algo works? – Chen A. Jan 05 '18 at 12:36
  • 3
    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. – Peter de Rivaz Jan 05 '18 at 12:39