What is a permutation ?

Any rearrangement of the list [1,2,3,…,n] is called a permutation of it. For example

  • There are 6 permutations of [1,2,3], namely [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]

What is a transposition ?

A transposition (i,j) is a simple move which switches the numbers i and j

For example,

  • The transposition (2,3) applied to [1,2,3] gives the permutation [1,3,2].
  • The transposition (2,3) applied to [5,3,4,1,2] gives the permutation [5,2,4,1,3]

Permutations from transpositions ?

Suppose we start with [1,2,….n] and we are only allowed to use transpositions to switch elements across. Can we end up with any permutation of [1,2,…,n] ?

The answer is … yes! This fact, in group theory is expressed as the following theorem:

Theorem: The group of permutations is generated by transpositions

As an example, let’s see how we can get [3,2,4,1] from [1,2,3,4] by repeatedly using just transpositions

  • First use the (1,4) transposition : [1,2,3,4]->[4,2,3,1]

  • Then use the (3,4) transposition : [4,2,3,1]->[3,2,4,1]

Note that there might be many ways to use transpositions to get to a permutation. In this post, we are only concerned about showing the existence of one such way!

To is equivalent to From

First, let’s note that if we can go from [1,2,..,n] to a permutation s using transpositions \(T_1, T_2, \ldots, T_r\), then you can use the transpositions in reverse order to go from s to [1,2,…,n]

As an example, observe that we can go from [3,2,4,1] to [1,2,3,4] by repeatedly using just transpositions as follows

  • First use the (3,4) transposition : [3,2,4,1]->[4,2,3,1]

  • Then use the (1,4) transposition : [4,2,3,1]->[1,2,3,4]

So we’ll show that we can go from an arbitrary permutation s to [1,2,….,n] using just transpositions

Bubble sort

Now there is a classical sorting algorithm called bubble sort. Given a list of n numbers, it sorts it in ascending order.

The way it works is as follows:

  • Look at 0-th and 1-st element in list. Swap them if 0-th element > 1-st element.
  • Look at 1-st and 2-nd element in list. Swap them if 1-st element > 2-nd element.
  • …

  • Look at n-1-th and n-th element in list. Swap them if n-1-th element > n-th element.

    At this stage, the largest element of the list has been pushed or rather, bubbled to the end of the list. This process takes n-1 steps

  • Now repeat the same process for the first n-1 elements of the list. That is, compare (0-th and 1-st element), swap if needed. Compare (1-st and 2-nd element), swap if needed…. Compare (n-2-th and n-1-th element), swap if needed.

    At this stage, the second largest element of the list has been bubbled to the last but one position in the list. This process takes n-2 steps

  • Keep repeating the same process for the first n-2 elements of the list. Then, for the first n-3 elements of the list and so on.

  • When you do the process for the first n-i elements of the list, the i+1-th largest element of the list gets pushed to its correct position in the sorted order.

  • Thus after n-1 + n-2 + …. + 2+1 = \(O(n^2)\) steps over all, you’ll end up with the list sorted in ascending order.

Proof of the theorem

Let’s apply bubble sort to our permutation s. Notice that any step in bubble sort is a swap of exactly two elements if at all, i.e. a transposition move! And we change s to [1,2,…,n] !

Thus using \(O(n^2)\) transpositions, we can covert s to [1,2,…,n] and vice versa, by reversing the order of transpositions. Voila! We just proved our theorem.

Bubble sort in action !

Let’s apply our constructive bubble-sort proof to go from [3,2,4,1] to [1,2,3,4] using just transpositions

For the first 4 elements

  • Swap 1-st and 2-nd element using (2,3) transposition : [3,2,4,1]->[2,3,4,1]
  • 2-nd and 3-rd element in good shape, no need to swap : [2,3,4,1] stays as it is
  • Swap 3-rd and 4-th element using (1,4) transposition : [2,3,4,1]->[2,3,1,4]

For the first 3 elements

  • 1-st and 2-nd element in good shape, no need to swap : [2,3,1,4] stays as it is

  • Swap 2-nd and 3-rd element using (1,3) transposition : [2,3,1,4]->[2,1,3,4]

For the first 2 elements

  • Swap 1-st and 2-nd element using (1,2) transposition : [2,1,3,4] -> [1,2,3,4]

Done!

Transposition usage

Note that we ended up using 4 transpositions for the bubble-sort algorithm to go from [3,2,4,1] to [1,2,3,4] while we had used just 2 to achieve it earlier. So this algorithm is not very economical in terms of usage of transpositions. However, it gives a nice constructive proof of how to generate permutations with transpositions!