Mobile Generating of All Permutations of a Set

Mobile Generating of All Permutations of a Set

Recall from the Generating All Permutations of a Set page that we can generate all $n!$ of the $n$-permutations of elements of the $n$-element set $A = \{1, 2, ..., n \}$ of positive integers by taking all of the $(n - 1)!$ many $(n - 1)$-permutations of elements of the $n-1$-element set $A \setminus \{n \} = \{1, 2, ..., n - 1 \}$, writing each of them down $n$ times, and then writing the number $n$ once in a distinct spot for each group of the $(n - 1)!$ permutations from $A \setminus \{ n \}$.

We will now look at another method for generating permutations that is somewhat improved on the prior method. The method of generating permutations we will see below will even give us somewhat of a natural ordering of the permutations. Before we look at this method, we will need to look at an important definition.

Definition: Given any $n$-permutation $(x_1, x_2, ..., x_n)$ of real numbers, we assign either a left or right arrow to each above each number $x_i \in \{ x_1, x_2, ..., x_n \}$. In the $n$-permutation, the number $x_i$ is said to be Mobile if $\overrightarrow{x_i}$ points to the right adjacent component $x_{i+1}$ and $x_i > x_{i+1}$ OR if the component $\overleftarrow{x_i}$ points to the left adjacent component $x_{i-1}$ and $x_{i-1} < x_i$.

For example, consider the following $4$-permutation with the given arrow assignment:

\begin{align} \quad (\overleftarrow{2}, \overleftarrow{4}, \overrightarrow{1}, \overleftarrow{3} ) \end{align}

Here we have that the number $4$ is mobile since $4$ points left-adjacent to $2$ and $2 < 4$. Furthermore, the number $3$ is mobile since $3$ points-left adjacent to $1$ and $1 < 3$.

If the first number in an $n$-permutation is pointing left then that element is not mobile. Similarly, if the $n^{\mathrm{th}}$ number is pointing right then it also cannot be mobile. Furthermore, the number $1$ is never mobile and the number $n$ is mobile if its arrow assignment points to another number.

Theorem 1: If $A = \{ 1, 2, ..., n \}$ then all $n!$ many $n$-permutations of $A$ can be generated as follows: Start with the simplest permutation with the assigned arrows $(\overleftarrow{1}, \overleftarrow{2}, ..., \overleftarrow{n})$. Find the largest integer $p \in \{1, 2, ..., n \}$ such that $p$ is mobile. Interchange the element $p$ with the element that $p$ points towards. Change the direction of the arrows of the elements $q \in \{1, 2, ..., n \}$ such that $p < q$. Repeat the process until no number in the current permutation is mobile.

We will look at an example of applying this algorithm to find the $3$-permutations of elements in $A = \{1, 2, 3 \}$. The order of the permutations by the algorithm in Theorem 1 starts on the leftmost column in the table below with successive permutations going down the columns from left to right.

\begin{align} (\overleftarrow{1}, \overleftarrow{2}, \overleftarrow{3} ) \\ (\overleftarrow{1}, \overleftarrow{3}, \overleftarrow{2} ) \\ (\overleftarrow{3}, \overleftarrow{1}, \overleftarrow{2} ) \\ (\overrightarrow{3}, \overleftarrow{2}, \overleftarrow{1} ) \\ (\overleftarrow{2}, \overrightarrow{3}, \overleftarrow{1} ) \\ (\overrightarrow{2}, \overleftarrow{1}, \overrightarrow{3} ) \end{align}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License