Permutation cycles and entropy-optimal representations

January 13, 2023
Útulek Series, 7 | CF1783F Chapter, 1

1783F asks:

Given two size-$N$ permutations, $A,B$, find the minimum number of operations required to sort both arrays. Each operation sorts some integer $1\leq x\leq N$ into its correct position in both arrays. That is, given $x$, an operation

1. Finds $i$ s.t. $A_i=x$, and swaps $A_i,A_x$,
2. Finds $j$ s.t. $B_j=x$, and swaps $B_j,B_x$,

for $1$-indexed $i,j$.

I’d like to take this problem to investigate further the concept of state space simplification, and gain intuition on the equivalence between seemingly distinct state representations, as well as taking some time to properly learn more advanced flow techniques such as Push-Relabel with LCT, and Goel-Kapralov-Khanna (GKK).

1 Naive permutation cycle representation

I begin with a series of ideally-reversible simplifications on the problem statement:

1. Consider only one permutation $A$.
2. Disregard the requirement for the operation to only swap an element into its sorted location. Any swaps are permissible.

Simplification 2 turns out to actually be an equivalence under the objective of minimizing the number of operations. This equivalence is nuanced to prove but easy to intuit. Along with the first simplification, we now ask:

Given size-$N$ permutation $A$, find the minimum number of swaps to sort $A$.

This is a fairly well-known problem (see, for example, 1768D). Introductory group theory has what I will call the cycle representation for permutations:

Definition 1.0 (Permutation cycle representation): Permutation $P=P'_1P'_2\cdots P'_{P'}$ where the $P'_i$ are disjoint sets of the $|P|$ integers, and

$$P_{P'_{i,j}}=P'_{i,j+1}$$

where $P'_{i,j+1}=P'_{i,1}$ if $j+1>|P'_i|$ (i.e. we define it to wrap around).

In essence, we decompose the permutation into disjoint cycles $P'_i$, where the numbers in each cycle point towards each other in sequence. The cycles are unordered amongst each other, but the numbers within the cycles must be ordered. For example, we have

1. $\langle 4,3,2,1\rangle=(4,1)(3,2),$
2. $\langle 1,2,3,4\rangle=(1)(2)(3)(4),$
3. $\langle 4,3,1,2\rangle=(4,2,3,1).$

This has the nice property that, should we define the composition operation between permutations, $R=P\cdot Q$, the composition may be decomposed into the product of the cycles of $P$ and $Q$.

Definition 1.1 (Permutation composition): Given permutations $P,Q$, we define $R=P\cdot Q$ with

$$R_i=Q_{P_i}.$$

For example,

1. $\langle 4,3,1,2\rangle\langle 4,3,1,2\rangle=\langle 2,1,4,3\rangle,$
2. $\langle 4,3,1,2\rangle\langle 1,2,3,4\rangle=\langle 4,3,1,2\rangle=\langle 1,2,3,4\rangle\langle 4,3,1,2\rangle,$
3. $\langle 4,3,1,2\rangle\langle 4,3,2,1\rangle=\langle 1,2,4,3\rangle\neq\langle 4,3,2,1\rangle\langle 4,3,1,2\rangle=\langle 2,1,3,4\rangle.$

Already, we have non-communtativity, as well as the concept of a commutative identity. I think we also have some property with rotating the cycles when we take permutation powers, but I’m having trouble proving that right now. Cycle decomposition should ideally give us permutation periods trivially. Perhaps my definition $(1.0)$ is flawed by some constant factor…

I want to investigate definition $(1.0)$ from an information-theoretic view. Naively, permutation representations $P$ take $|P|$ objects of information. Cycle representations lik $(1.0)$ admit $P'$ cycles, each of which admits some number of elements. Naively, this ends up with $|P|$ objects again, but luckily each cycle $P'_i$ must necessarily have as its last element the smallest unseen positive integer, so actually we end up with $|P|-P'$ objects of information in definition $(1.0)$.

With a single swap, we can always decrease the size of one cycle by $1$, and create with the element a new singleton. Thus, the minimal number of swaps to sort $P$ is always $|P|-P'$. Intuitively, then, $P$ must take at least $|P|-P'$ objects to represent and distinguish from all other size-$N$ permutations. I denote this an entropy-optimal representation.

This observation handily solves the simplified 1783F with only considering $A$.

2 Entropy-optimal 1783D

We then take definition $(1.0)$ on both permutations $A,B$ and end up with cycles $A'_i,B'_i$ which may share some elements. The example I have been using is

$$A=\langle 2,3,5,6,1,4,7\rangle=(2,3,4,1)(6,4)(7),\\ B=\langle 2,4,5,1,7,6,3\rangle=(2,4,1)(5,7,3)(6),$$

for which one of the optimal answers for 1783F is $4$ operations of $x=1,3,4,5$. As expected, we see that each cycle $A'_i,B'_i$ sees $|A'_i|-1$ or $|B'_i|-1$ operations, which will reduce all cycles to singletons at the end, thus sorting both arrays.

This naive dual-cycle representation of 1783F is fine, but unlikely to be entropy-optimal. Intuitively, we may only operate on the permutations in unison, so a naive dual-cycle representation must contain extra information which pertains to independent permutation operations.