# Permutations

$$\gdef\delim#1#2#3{\mathopen{}\mathclose{\left#1 #2 \right#3}} \gdef\p#1{\delim({#1})} \gdef\set#1{\delim\{{#1}\}} \gdef\ceil#1{\delim\lceil{#1}\rceil} \gdef\unit#1{\ \text{#1}}$$

$n!$

From CB22:

The challenge is to construct a data structure for storing a permutation that takes less space than the trivial data structure, specifically 1.44 n fewer bits, while retaining the ability to quickly evaluate the permutation.

Take a permutation over $2^{32}$ elements. This can be represented as a vector of $2^{32}$ $32$-bit integers, taking $17.2\unit{GB}$. In theory it can be stored in

$$\ceil{\log_{256} 2^{32}! } = 16.4 \unit{GB}$$

We can do better if we build an approximate lookup that returns a set of $n$ elements, one of which is the permutation. Split the permutation in blocks of size $n$. If we ignore the order within the blocks, they can be stored in $\ceil{\log_{256} {2^{32} \choose n} }$ bytes. If we pick a blocksize of $1427$ we get $4096\unit{B}$, a disk block.

• Ber20 Bernstein 2020. Verified fast formulas for control bits for permutation networks.
• CB22 Cohen, Boneh (2022). How to Store a Permutation Compactly.

https://arxiv.org/pdf/0902.1038.pdf Remco Bloemen
Math & Engineering
https://2π.com