Creating binary information from a permutation

Question

I created a random permutation with a deck of 52 unique cards. I want to transform this random permutation into a number that is represented in binary format with a length of $\lfloor \log_2(52!))\rfloor$. Is that possible and how can I do that?

Answer 1

There is an explicit mapping of $n$-permutations to integers in $[0,n!-1]$. Before turning to permutations, recall that usual base $b$ representation works as follows:

Take a sequence of natural numbers $b_k\geqslant 2$. Then each natural number $n\in\Bbb N_0$ has a unique representation of the form $$n=\sum_{k=0}^\infty a_k B_k\qquad\text{where}\quad 0\leqslant a_k< b_k,\ B_k=\prod_{i=0}^{k-1}b_i $$ where the integers $a_k$ are unique integers called "digits" and only finitely many $a_k$ are non-zero. The empty product shall be $1$, i.e. $B_0=1$.

The common use case is when all $b_i=b$ are the same, for example $b=2$ for binary representation or $b=10$ for decimal representation. The $a_i$ are the digits of $n$ represented in base $b$, and $B_k=b^k$ is the magnitude of the $k$-th digit $a_k$.

But we can as well pick a sequence of different natural numbers for $b_i$, in particular we can pick $b_i=i+1$. Notice that $b_0=1$ is no problem provided infinitely many $b_i$'s satisfy $b_i\geqslant2$. This choice of $b_i$ gives again a unique representation of $n\in\Bbb N_0$ with digits $0\leqslant a_k \leqslant k$ and $B_k=k!$, $k\geqslant0$.

Now on one hand, this gives a unique representation of natural numbers, and on the other hand, a number with $j$ digits gives a natural representation of a $j$-permutation as follows: Suppose we have a list of $j$ items, then pick the $a_j$-th item and then remove that item from the list. Proceed with $a_{j-1}$ etc. until all items are consumed and the list is empty. The items in the list are indexed starting at zero.

Example: Take $$n=13= 2\cdot 3! + 0\cdot2! + 1\cdot 1!+0\cdot0!$$ with the 4 digits 2010 from hihgest to lowest. The list of items be ABCD. The rule is to first pick element no. 2, which is C as counting starts at 0:

Digits   List_before   List_after  Element  Permutation
-------------------------------------------------------
a_3 = 2: ABCD          ABD         C        C
a_2 = 0: ABD           BD          A        CA
a_1 = 1: BD            B           B        CAB
a_0 = 0: B                         D        CABD

To be more explicit, here is a Python3 code that converts integers to FAK representations and vice versa. The returned FAK is little endian, i.e. the $k$-th entry (digit) satisfies $0\leqslant a_k \leqslant k$ where $k$ starts at 0:

#!/usr/bin/env python3

def int_to_fak (i, length):
    """Convert integer I to little endian FAK representation
        of len LENGTH, which is a list of integers."""
    fak = []
    for k in range(length):
        fak.append (i % (k+1))
        i //= k+1
    return fak

def fak_to_int (fak):
    """Convert litte endian FAK to integer."""
    i = 0
    B_k = 1
    for k in range(len(fak)):
        i += fak[k] * B_k
        B_k *= k+1
    return i

Notice that it's easy to implement addition and subtraction on this format. Just add digits starting at the $0$-th and work towards higher digits applying carry from lower digits. In particular, one can implement increment by one to get to the "next" permutation without the need to convert from ints again and again.

The little endian FAKs can then act as permutations on tuples, lists or strings:

def fak_apply (fak, it0):
    """Apply little endian FAK to iterable IT0."""
    assert (len(fak) == len(it0))
    it = list(it0)
    perm = []
    for k in range(len(fak)-1, -1, -1):
        a_k = fak[k]
        assert (a_k <= k and a_k >= 0)
        perm.append (it[a_k])
        del it[a_k]
    # Let returned permutation be of same type like IT0.
    return "".join(perm) if isinstance(it0,str) else it0.__class__(perm)

The inverse function is retrieving a FAK from a given permutation and an unpermuted set of objects:

def perm_to_fak (perm, it0):
    """Let PERM be a permutation of iterable IT0.  Return little endian FAK
       of respective permutation."""
    assert (len(perm) == len(it0))
    it = list(it0)
    fak = []
    for k in range(len(perm)):
        a_k = it.index (perm[k])
        assert (a_k >= 0)
        fak.append (a_k)
        del it[a_k]
    return list(reversed (fak))

Finally, here is some code and produced output. The base set is called Alphabet in the code, and for brevity it has only 10 elements:

from math import log, factorial

Alphabet = "ABCDEFGHIJ"
n_symbols = len(Alphabet)
n_bits = 1 + int (log(factorial(n_symbols)-1) / log(2)) 

for perm in (Alphabet, "ABCDEFGHJI", "BACDEFGHIJ", "JABCDEFGHI",
             "BCDEFGHIJA", "JIHGFEDCBA"):
    print ("== %s ==" % perm)
    fak = perm_to_fak (perm, Alphabet)
    print ("  fak =", fak)
    i = fak_to_int(fak)
    i_bin = format(i,'b').zfill(n_bits)
    print ("  int = %d = 0b%s" % (i, i_bin))

Here is the output:

== ABCDEFGHIJ ==
  fak = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
  int = 0 = 0b0000000000000000000000
== ABCDEFGHJI ==
  fak = [0, 1, 0, 0, 0, 0, 0, 0, 0, 0]
  int = 1 = 0b0000000000000000000001
== BACDEFGHIJ ==
  fak = [0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
  int = 362880 = 0b0001011000100110000000
== JABCDEFGHI ==
  fak = [0, 0, 0, 0, 0, 0, 0, 0, 0, 9]
  int = 3265920 = 0b1100011101010110000000
== BCDEFGHIJA ==
  fak = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]
  int = 409113 = 0b0001100011111000011001
== JIHGFEDCBA ==
  fak = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
  int = 3628799 = 0b1101110101111011111111

Notice that the last int value is the largest you can get for a 10-permutation, which is $$10!-1 = \sum_{k=0}^{10-1} k\cdot k!$$

As a final note, you'll need 1 bit more than you calculated, though, because the number of bits needed to encode a natural number $n$ in the usual way and without sign is $1+\lfloor\log_2n\rfloor$ bits. In particular, to encode $0,\cdots, 52!-1$ you'll need $$226 =1+\lfloor\log_2(52!-1)\rfloor\text{ bits}$$ or 68 decimals places.