"Encode" all $n$-permutations with the fewest number of swaps

Question

The goal is to find $m$ swaps $s_1, s_2, \dots, s_m$ such that any $n$-permutation can be encoded as a binary sequence of length $m$, $x_1, x_2, \dots, x_m$, where $x_i$ indicates whether to perform the $s_i$ swap (if $x_i=1$) or skip it (if $x_i=0$).

For example, if we list the swaps as $s_1=(1,2),\; s_2=(2,3),\; s_3=(3,1)$, then the permutation from $ABC$ to $CAB$ can be encoded as $1,0,1$: first swap the $(1,2)$ elements to get $BAC$, then skip the swap of $(2,3)$ elements because $x_2=0$, and finally swap the $(3,1)$ elements to get $CAB$. Is there a way to make $m$ as small as possible (perhaps as close as possible to $\log_2{n!}$) while ensuring that every $n$-permutation can be represented?

Background information: This problem stems from my attempt to construct a "permutation circuit". This circuit accepts $n$ elements as input and produces a permutation of these elements as output. The circuit exclusively utilizes a component known as a "swap" gate. This gate takes two elements as input and is controlled by an additional input bit. If this bit is set to $1$, the gate swaps the two input elements before outputting them. If the bit is set to $0$, the gate outputs the input elements directly without swapping. My goal is to construct such a circuit using the fewest possible number of these gates, enabling it to generate any permutation of these $n$ elements.

enter image description here

Answer 1

I hope this is helpful. Joriki's brute force calculations of minimal $m$ for small $n$ are quite interesting and indeed come close to your estimate of $\log_2(n!)$. If you're willing to sacrifice such efficiency in exchange for a simpler, algorithmic design, here's an alternative approach, following a well-trodden path. The number of bits is $m = \binom{n}{2} = \frac12 n(n-1)$.

Coxeter presentation of $S_n$

There's a well-known presentation of the symmetric group $S_n$ on $n$ symbols given by the $n-1$ Coxeter generators $\sigma_1, \dots, \sigma_{n-1}$, where $\sigma_i = (i\;\;i+1)$. Besides being involutions ($\sigma_i^2 = 1$), distant (non-consecutive) generators commute ($\sigma_i\sigma_j = \sigma_j\sigma_i$ for $|i - j| > 1$) and consecutive generators ($|i - j| = 1$) satisfy the braid relation $$ \sigma_i\sigma_j\sigma_i = \sigma_j\sigma_i\sigma_j. $$

Example for $n = 3$

The two generators are $\sigma_1 = (1\;2)$ and $\sigma_2 = (2\;3)$, and the $3! = 6$ elements of $S_3$ can be presented as words formed of these "swaps": $$ \begin{array}{ccc} \text{one-line} & \text{cycle} & \text{word} \\ \hline 123 & - & \\ 213 & (1\;2) & \sigma_1 \\ 132 & (2\;3) & \sigma_2 \\ 231 & (1\;2)(2\;3) & \sigma_1\sigma_2 \\ 312 & (2\;3)(1\;2) & \sigma_2\sigma_1 \\ 321 & (1\;2)(2\;3)(1\;2) & \sigma_1\sigma_2\sigma_1 \\ \end{array} $$

The lengths of these words are minimal, and I sorted them by len-lex order. Notice, there's just one permutation of length $3$, called the longest element, and it determines the length of the sequence needed for your encoding: $$ m = \binom{n}{2} = \frac{n(n-1)}{2} $$ since each symbol, thinking in the one-line notation, has to swap with each other symbol to form the permutation to completely reverses the sequence $(123 \mapsto 321)$.

So you could define your sequence of transpositions by this longest word: $\sigma_1^{s_3} \sigma_2^{s_2} \sigma_1^{s_1}$, where each $s_i \in \{0, 1\}$ and the composition of permutations is read from right to left as usual. But I think it's more natural to record the encoding as a string, read from left to right. (These conventions are arbitrary, and reversing just swaps out each permutation for its inverse): $$ \begin{array}{cccc} 1\text{-line} & \text{word} & \text{verbose} & \text{encoding} \\ \hline 123 & - & \sigma_1^0\sigma_2^0\sigma_1^0 & 000 \\ 213 & \sigma_1 & \sigma_1^1\sigma_2^0\sigma_1^0 & 001 \\ 132 & \sigma_2 & \sigma_1^0\sigma_2^1\sigma_1^0 & 010 \\ 231 & \sigma_1\sigma_2 & \sigma_1^1\sigma_2^1\sigma_1^0 & 011 \\ 312 & \sigma_2\sigma_1 & \sigma_1^0\sigma_2^1\sigma_1^1 & 110 \\ 321 & \sigma_1\sigma_2\sigma_1 & \sigma_1^1\sigma_2^1\sigma_1^1 & 111 \\ \end{array} $$

Why does this work?

Beginning with a permutation in one-line notation, use a bubble sort algorithm to return the sequence to ascending order. Begin with the largest symbol $n$, and record the transpositions required to send it "home" (position $n$), then move on to the next largest symbol $n-1$, again recording transpositions needed to send it to position $n-1$. Continue all the way down. If we're recording these as a sequence of permutations in the usual function notation, then we record this sequence from right-to-left.

Here's an example of this process with the longest element $4321$ in $S_4$: $$ \color{blue}{43}21 \overset{\sigma_1}{\mapsto} 3\color{blue}{42}1 \overset{\sigma_2}{\mapsto} 32\color{blue}{41} \overset{\sigma_3}{\mapsto} \color{blue}{32}14 \overset{\sigma_1}{\mapsto} 2\color{blue}{31}4 \overset{\sigma_2}{\mapsto} \color{blue}{21}34 \overset{\sigma_1}{\mapsto} 1234 $$ From right to left, this is the word $\sigma_1\sigma_2\sigma_1\sigma_3\sigma_2\sigma_1$ which is of length $\binom{4}{2} = 6$, as expected.

What about for all the other permutations? At each stage, we're swapping a pair of symbols from decreasing to increasing order, recording a $1$ as it moves to the right. If a pair of symbols are already in increasing order, then we simply omit that swap, and record a $0$. As a consequence, for any permutation, the sequence of swaps will always be a subsequence of the longest word. For $n = 4$, this will be encoded as $s_1s_2s_3s_4s_5s_6$, where the permutation is presented as $$ \sigma_1^{s_6} \sigma_2^{s_5} \sigma_1^{s_4} \sigma_3^{s_3} \sigma_2^{s_2} \sigma_1^{s_1}. $$ The general patter should be clear.

Encoding for $n = 4$

To illustrate that this is indeed algorithmic, here are the results generated by a dozen or so lines of Python code for $n = 4$. As before, I've sorted the permutations by their encodings, first by length (total number of instances of $1$) then lexicographically. $$ \begin{array}{ccc} \text{one-line} & \text{encoding} & \text{length} \\ \hline 1234 & 000000 & 0 \\ 2134 & 000001 & 1 \\ 1324 & 000010 & 1 \\ 1243 & 001000 & 1 \\ 2314 & 000011 & 2 \\ 3124 & 000110 & 2 \\ 2143 & 001001 & 2 \\ 1342 & 001010 & 2 \\ 1423 & 011000 & 2 \\ 3214 & 000111 & 3 \\ 2341 & 001011 & 3 \\ 3142 & 001110 & 3 \\ 2413 & 011001 & 3 \\ 1432 & 011010 & 3 \\ 4123 & 111000 & 3 \\ 3241 & 001111 & 4 \\ 2431 & 011011 & 4 \\ 3412 & 011110 & 4 \\ 4213 & 111001 & 4 \\ 4132 & 111010 & 4 \\ 3421 & 011111 & 5 \\ 4231 & 111011 & 5 \\ 4312 & 111110 & 5 \\ 4321 & 111111 & 6 \\ \end{array} $$

Answer 2

Any comparison-based oblivious sorting algorithm that uses $m$ comparisons immediately leads to a solution to your problem with $m$ swaps. So your problem amounts to asking for a comparison-based oblivious sorting algorithm with the best possible running time.

A standard way to build an oblivious sort is using a sorting network. There are many constructions of sorting networks. Constructing sorting networks of optimal size is an open problem. If you want a simple construction, you might look at Batcher's odd-even mergesort or bitonic mergesort or Parberry's pairwise sorting network. These have size $m=O(n \log^2 n)$ (in some cases with very small constant factor, e.g., about 1). Compare to a straightforward lower bound on the optimal size, namely, $m \ge \log_2 n! = n \log n - \Theta(n)$.

Also relevant: Zig-zag sort achieves size $O(n \log n)$, which is within a constant factor of optimal, but is very complicated and might have large constant factors hidden in the big-O notation. Finally, bucket oblivious sort and other recent related research might be of interest to you.