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

2
votes

Given the swap distance defined as in the question Counting the adjacent 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?

2
stringalgorithmpermutationswap
Isn't this equivalent to the question "What is the worst case scenario for bubble sort?" – biziclop
An interesting question. I freely admit that I could be wrong, but on the face of it, it seems similar to the problem of finding optimum sorting sequences. (i.e. sort 5 items in 7 comparisons). There are known optimum sequences for small lists, but for larger numbers we rely on reasonably efficient algorithms that generate good, but not provably optimum, sorting networks. I suspect the same is true of finding the highest cost ordering. – Jim Mischel

2 Answers

1
votes

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.

1
votes

If the letters are distinct, we have the simple scenario where a letter positioned higher in the sequence is associated with more letters with which it can be out of order:

"abcde":
'e' can be out of order with 4 letters, 'd' with 3, etc.
"edcba", the reversed string, is the worst case where each letter is at max disorder

But when there are duplicates, letters positioned higher can only be placed out of order with earlier letters that are different:

"abbaba":
a3 max 3, b3 max 2
a2 max 2, b2 max 1
a1 max 0, b1 max 1
"aaabbb"

"aba"
a2 max 1, b1 max 1
a1 max 0
"aab" or "baa"

It's not a full method but maybe it's a useful direction.