Is there an efficient algorithm to find the permutation of a given string with the worst swap distance?

2016-05-08

An answer to this question on Stack Overflow.

Question

Given the swap distance defined as in the question https://stackoverflow.com/questions/7797540/counting-the-swaps-required-to-convert-one-permutation-into-another (i.e. we have a string of characters, and the swap distance from a permutation of that string is the minimum number of "adjacent character swaps" needed to get back to the original string).

I want an algorithm to find the highest possible swap distance for a given string. Of course, we could enumerate all permutations and check the swap distances of each, but that is horribly inefficient. Is there a quicker way to do it?

Answer

The fundamental operation you're allowed to do is swap two elements of the string. This is also the only operation you're allowed to do in insertion sort, so it seems as though you could pull in well-established results from the sorting literature to solve the problem.

According to the wiki page on insertion sort, the worst case is when the input is in reversed order. By the same logic, the reversing the target string should yield a string which is farthest from the target by swap distance.

A paper entitled "On Generating Worst-Cases for the Insertion Sort" (link) may be of help here.