What combinations of "swaps" of elements in a list are equivalent?

Question

Define a swap-operation $s_{ij}=s_{ji}$ on an $n$-tuple $a_n=(1,2,\dots,n)$ as interchanging the elements in the $i$th and $j$th positions of the tuple.

I would like to find an efficient way to generate all distinct permutations resulting from applying $k<n$ such swaps, i.e., all distinct $S=s_1s_2\cdots s_k$, where the subscripts refers only to the order in which the swaps are applied; any of the swaps $1,\dots,k$ could be any of the possible $s_{ij}$ (but it is perhaps appropriate to exclude the possibility of having two adjacent and identical swaps, since they would just cancel).

---

Example: For $n=3$, represent the tuple as a column vector and the swaps by the three $\left(\binom{n}{2}=3\right)$ possible $3\times 3$ matrices:

\begin{align} s_{12}&=\pmatrix{0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1}\\ s_{13}&=\pmatrix{0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0} \\ s_{23}&=\pmatrix{1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0} \end{align}

Then we can identify the results of applying $k=2$ such swaps:

\begin{align} s_{12}s_{13}a_3^T&=\pmatrix{3 & 1 & 2}^T \\ s_{12}s_{23}a_3^T&=\color{red}{\pmatrix{2 & 3 & 1}^T} \\ s_{13}s_{12}a_3^T&=\color{red}{\pmatrix{2 & 3 & 1}^T} \\ s_{13}s_{23}a_3^T&=\color{blue}{\pmatrix{3 & 1 & 2}^T} \\ s_{23}s_{12}a_3^T&=\color{blue}{\pmatrix{3 & 1 & 2}^T} \\ s_{23}s_{13}a_3^T&=\color{blue}{\pmatrix{3 & 1 & 2}^T} \\ \end{align}

Note the duplicates. I would like to avoid calculating these. Could I have known from the start that $\color{red}{s_{12}s_{23}=s_{13}s_{12}}$ and $\color{blue}{s_{13}s_{23}=s_{23}s_{12}=s_{23}s_{13}}$, without actually calculating these?

---

So far, I've checked the result of all permutations of operations (giving the six scenarios in the example above), and then thrown out the duplicates, but my computer quickly chokes. Is there a way to go directly to the unique results for a given $n$ and $k$? In my present problem, $n=9,$ but a generalization would be nice.

I'm using Matlab, but pseudo-code or strictly mathematical considerations are both very welcome.

Thank you.

Answer 1

One common way to describe a permutation is via its cycle decomposition. A permutation $\sigma$ specified by $\sigma(1)=4$, $\sigma(2)=5$, $\sigma(3)=2$, $\sigma(4)=1$, $\sigma(5)=3)$, $\sigma(6)=6$, $\sigma(7)=7$ can be described by writing down its cycles $$\begin{cases} 1 \xrightarrow{\sigma} 4 \xrightarrow{\sigma} 1\\ 2 \xrightarrow{\sigma} 5 \xrightarrow{\sigma} 3 \xrightarrow{\sigma} 2 \\ 6 \xrightarrow{\sigma} 6 \\ 7 \xrightarrow{\sigma} 7\end{cases}$$ which we usually shorten to $(1\;4)\;(2\;5\;3)\;(6)\;(7)$ or sometimes just $(1\;4)\;(2\;5\;3)$. (But for the purposes of this answer, we'll want to keep track of the length $1$ cycles as well.)

Each permutation has a cycle decomposition that's unique up to rotating a cycle (we can write $(2\;5\;3)$ as $(5\;3\;2)$ and that's still the same) and up to writing the cycles in a different order.

Moreover, knowing the cycle decomposition tells us how many swaps we need to get a given permutation. For example, we get the cycle $(2\;5\;3)$ by applying the swap $(5\;3)$ and then applying the swap $(2\;5)$; in general, we can get $(a_1\;a_2\;\cdots\;a_k)$ by applying $(a_1\;a_2)$ after $(a_2\;a_3)$ after ... after $(a_{k-1}\;a_k)$, which takes $k-1$ swaps.

Counting the $1$-cycles or fixed points, this tells us that we can obtain a permutation with $t$ cycles by doing $n-t$ swaps: If the cycles have length $\ell_1, \ell_2, \dots, \ell_t$, then $$(\ell_1-1) + (\ell_2-1) + \dots + (\ell_t-1) = n-t.$$ We also can't do any better: each swap can reduce the number of cycles by at most $1$, since at best it can combine two cycles into one cycle.

With $k$ swaps, we can get all permutations with $n-k$ cycles; also, all permutations with $n-k+2, n-k+4, \dots$ cycles, since we can insert as many pairs of redundant swaps as we like. Each swap reverses the sign of a permutation, so we can't get permutations with $n-k+1, n-k+3, \dots$ cycles in any way.

So if you want to find all the permutations that can be obtained with $k$ swaps, find all the cycle decompositions that have $t$ cycles, where $t \ge n-k$ and $t \equiv n-k \pmod 2$.

---

Here's an example. Suppose we have $n=5$ and we allow ourselves $k=2$ swaps. Then we can get permutations with $n-k=3$ cycles, or $5$ cycles. (The $5$ cycle case is when we do the same swap twice, and get back to the identity permutation, which you might not want to count.)

The $3$ cycles have total length $5$, which could be $3+1+1$ or $2+2+1$. We'll handle these cases separately:

• If the cycles have lengths $3$, $1$, and $1$, we'll want to choose the $3$ elements of the $3$-cycle (in $\binom{5}{3}=10$ ways) and then choose the ordering on the $3$-cycle (in $(3-1)!$ ways). These are: $$(1\;2\;3)\;(4)\;(5) \qquad (1\;3\;2)\;(4)\;(5) \\ (1\;2\;4)\;(3)\;(5) \qquad (1\;4\;2)\;(3)\;(5) \\ (1\;2\;5)\;(3)\;(4) \qquad (1\;5\;2)\;(3)\;(4) \\ (1\;3\;4)\;(2)\;(5) \qquad (1\;4\;3)\;(2)\;(5) \\ (1\;3\;5)\;(2)\;(4) \qquad (1\;5\;3)\;(2)\;(4) \\ (1\;4\;5)\;(2)\;(3) \qquad (1\;5\;4)\;(2)\;(3) \\ (2\;3\;4)\;(1)\;(5) \qquad (2\;4\;3)\;(1)\;(5) \\ (2\;3\;5)\;(1)\;(4) \qquad (2\;5\;3)\;(1)\;(4) \\ (2\;4\;5)\;(1)\;(3) \qquad (2\;5\;4)\;(1)\;(3) \\ (3\;4\;5)\;(1)\;(2) \qquad (3\;5\;4)\;(1)\;(2)$$ For each of these, we can represent it as a product of the $s_{ij}$'s by factoring $(i\;j\;k)$ as $s_{ij}s_{jk}$: e.g., $(1\;3\;5)\;(2)\;(4)$ is the product $s_{13} s_{35}$. (That's $s_{13}$ done after $s_{35}$.)
• If the cycles have length $2$, $2$, and $1$, we have $5$ cases on what the odd element out is, and then $3$ ways to pair up the remaining $4$ elements into two cycles: $$(1\;2)\;(3\;4)\;(5) \qquad (1\;3)\;(2\;4)\;(5) \qquad (1\;4)\;(2\;3)\;(5) \\ (1\;2)\;(3\;5)\;(4) \qquad (1\;3)\;(2\;5)\;(4) \qquad (1\;5)\;(2\;3)\;(4) \\ (1\;2)\;(4\;5)\;(3) \qquad (1\;4)\;(2\;5)\;(3) \qquad (1\;5)\;(2\;4)\;(3) \\ (1\;3)\;(4\;5)\;(2) \qquad (1\;4)\;(3\;5)\;(2) \qquad (1\;5)\;(3\;4)\;(2) \\ (2\;3)\;(4\;5)\;(1) \qquad (2\;4)\;(3\;5)\;(1) \qquad (2\;5)\;(3\;4)\;(1)$$ These are particularly easy to write in terms of $s_{ij}$'s: for example, $(1\;3)\;(4\;5)\;(2)$ is $s_{13} s_{45}$ in any order. (In general, each cycle in the cycle decomposition gives us some swaps, and swaps from different cycles can be interleaved however we like without changing the permutation.)