Let N≥0 and let A[1..N] be an array of integers. It is possible to sort A (i.e., permute its elements so that they occur in nondecreasing order) using a sequence of swaps in which each swap is of two adjacent elements. (The Bubblesort algorithm gives testimony to this fact.) For example, suppose A = [ 5, 3, 4, 2 ]. Then by applying the swap sequence s = <3, 1, 2, 3, 1> , we achieve sortedness, as follows:
5 3 4 2 original array
5 3 2 4 after swapping 3rd and 4th elements
3 5 2 4 after swapping 1st and 2nd elements
3 2 5 4 after swapping 2nd and 3rd elements
3 2 4 5 after swapping 3rd and 4th elements
2 3 4 5 after swapping 1st and 2nd elements
(As you probably already figured out,
each element i in a swap sequence indicates the swapping of the
i-th element of the array with the (i+1)-st.)
We use the term complete swap sequence to refer to any sequence of swaps (of adjacent elements) that, when applied to a specified array, results in that array becoming sorted. For any array, there are infinitely many distinct complete swap sequences. (For example, take any complete swap sequence for that array, and, at any point within it, swap the same pair of elements 2k times, for any k≥0. The resulting swap sequence is also complete, as the "extra" swaps have no net effect upon the array.) Here, however, we are interested only in those complete swap sequences that are of minimum length. (Note that, for the array A mentioned above, there are six distinct minimum-length swap sequences, of which the swap sequence s mentioned above is one.)
The problem to be addressed in this lecture is as follows: Given an array A[1..N], determine the number of distinct minimum-length complete swap sequences for that array.