Notes on Permutations: A Chalkboard Algorithm
Tyler Neylon
\(\newcommand{\customstrut}{}\) \(\newcommand{\crossedouty}{\dot y \kern -5pt \scriptscriptstyle{\diagup\atop\vphantom{y}}}\) \(\newcommand{\crossedoutone}{\dot 1 \kern -5pt {\scriptscriptstyle{\diagup\atop\vphantom{\textstyle 1}}}}\) \(\newcommand{\crossedouttwo}{\dot 2 \kern -5pt {\scriptscriptstyle{\diagup\atop\vphantom{\textstyle 2}}}}\) \(\newcommand{\crossedoutthree}{\dot 3 \kern -5pt {\scriptscriptstyle{\diagup\atop\vphantom{\textstyle 3}}}}\) \(\newcommand{\crossedoutfive}{\dot 5 \kern -5pt {\scriptscriptstyle{\diagup\atop\vphantom{\textstyle 5}}}}\) \(\newcommand{\crossedoutsix}{\dot 6 \kern -5pt {\scriptscriptstyle{\diagup\atop\vphantom{\textstyle 6}}}}\) \(\newcommand{\crossedoutseven}{\dot 7 \kern -5pt {\scriptscriptstyle{\diagup\atop\vphantom{\textstyle 7}}}}\) \(\newcommand{\lowerhaty}{\lower 1ex{\hat y}}\) \(\newcommand{\lhy}{\lower 1ex{\hat y}}\) \(\renewcommand{\hat}[1]{\widehat{#1}}\)

[ Formats: html | pdf \(\,\)]

This is a continuation of notes about permutations; this series began with some notes on cycles and transpositions.

This short article describes a chalkboard method for multiplying (that is, composing) permutations written in cycle notation. When I call it a chalkboard method, I mean that it’s useful for humans doing simple math by hand — akin to long-hand addition taught in school — and as opposed to an algorithm designed for a computer.

This article can be read as an extension to an earlier note about permutations, although this one can be read independently, assuming that you know both what permutation multiplication (synonymously, composition) is, and what cycle notation is. (If not, you can learn by reading the previous note in this series.)

The chalkboard algorithm I’ll describe is something I derived for fun. I haven’t put effort into discovering if someone else has come up with it before me.

Let’s get started. As an example, consider

\[\sigma = (1\;3\;7\;2\;5\;4) \quad\text{and}\quad \tau = (1\;2)(4\;6).\qquad(1)\]

\[\begin{align*} \sigma &= (1\;3\;7\;2\;5\;4) \quad\text{and} \\[0.2cm] \tau &= (1\;2)(4\;6). \quad (1) \end{align*}\]

We can define the product \(\sigma\cdot\tau\) as the permutation \(\mu\) where \[\mu(x) = (\sigma\cdot\tau)(x) = \tau(\sigma(x)).\qquad(2)\] I’ve chosen to work with the intuition that the element on the left \((\sigma)\) “happens first;” this notation seems more natural to me. Some authors choose the opposite ordering because it avoids the awkward reversal of symbols in (2).

In our example, \[ \mu = (1\;3\;7)(2\;5\;6\;4), \] as can be verified by asking, for each \(x\in\{1,2,\ldots,7\}\), what is \(y=\sigma(x)\)? followed by asking what is \(\tau(y)\)?

Let’s informally call this a 2-lookup method, in the sense that a human will perform a scan of \(\sigma\) to find \(\sigma(x)\) and then another scan of \(\tau\) to find \(\tau(y)\) for each input \(x\) to \(\mu\). This article improves on this by providing an algorithm that is a 1-lookup method. In some informal sense we can say it’s twice as fast for a human to execute.

A computer can multiply permutations even more efficiently. We could encode a permutation as a hash map (a dict in Python, or an object in JavaScript, for example) where the keys are the input numbers and the values are what those values map to. In this case, each lookup of a value \(\mu(x)\) takes constant time, so that computing all of \(\mu\) requires \(O(n)\) time, where \(n\) is the size of the domain of the permutations. I don’t consider a human working on a chalkboard to have access to constant-time lookups, so this algorithm is only for computers.

1 A Worked Example

I’ll illustrate the method by working through example (1), and then I’ll summarize the general process.

Say that a permutation is single-cycle when its cycle notation has one cycle: \(\sigma_1=(1\;4\;2)\) is single-cycle, whereas \(\sigma_2=(1\;2)(3\;5)\) is not.

The first time you read about this method, it may seem like a lot, but after working a few examples, it feels natural and easy.

2 Why It Works

In this section, I’ll define \(\mu\) as the permutation produced by this method, and it will be my job to show that \(\mu=\sigma\cdot\tau\).

At the start of each iteration of step 2, we’re going to insert element \(y\) after \(x\) in our notation of \(\tau\), where \[\begin{align*} x &= \text{the right-most un-overlined element of }\sigma, \text{ and} \\ y &= \text{the dotted element in }\tau. \end{align*}\] Effectively, we’re recording that \(\mu(x)=y\).

In each case, \(y\) is chosen as, informally, the element in \(\tau\) after [the element in \(\sigma\) after \(x\)]. In other words, \[y = \tau(\sigma(x)).\qquad(3)\] whenever we write \(x\lowerhaty\).

At the end of an iteration of step 2, the newly-dotted element \(\dot z\) will satisfy \(z=\tau(x)\). This sets us up for the next iteration of step 3, in which we’ll begin looking at a new \(x'\) with \(\sigma(x')=x\), preparing us to continue fulfilling (3) for the next value \(y' = \dot z\).

When we write out the answer in step 3, either element \(x\) in \(\tau\) has an inserted element after it or not. If element \(y\) is inserted, then we have \[\mu(x) = y = \tau(\sigma(x))\qquad(4)\] by (3). If \(x\) has no inserted element after it, then \(x\) never appeared in \(\sigma\)’s cycle notation, meaning \(\sigma(x)=x\). Then \[ \mu(x) = \tau(x) = \tau(\sigma(x)). \qquad(5)\] Since either (4) or (5) holds for all inputs \(x\) to \(\mu\), we must have \(\mu = \sigma\cdot \tau\), concluding the proof of correctness.

3 The General Process

The steps written in \(\S1\) will work for any single-cycle permutation \(\sigma\). It’s not difficult to extend this method to work for any \(\sigma\).

Below is the general method, simplified with some shorthand notation that I believe will be clear in the context from \(\S1\). This is the same as above, with some changes in step 2 to accommodate multi-cycle \(\sigma\)s.

It’s straightforward to apply essentially the same proof of correctness to this general version of the method.

You can get emails about new posts if you'd like: