Minimum number of adjacent swaps needed to sort a circle of elements

Question

I have been thinking about some problems in combinatorics and I came across a problem I'm having trouble with.

Suppose you have a list $L$ of length $n$ (wlog the elements of the list are 1,2,3,...,n) and you want to sort it circularly (meaning [3,1,2] is sorted) with swaps of adjacent elements, but you are also allowed to consider the first and last elements as adjacent. What is the minimal number of swaps required?

The way to think about this, I think, is to consider the elements of $L$ arranged around a circle, in order. There are $n$ ways to do this, each with a different element at the top. What I want to do is just arrange $L$ in each way, sort it while counting the swaps, then take the minimum.

The problem I have is that elements of the list don't stay fixed: for example I can move 1 into the correct place, but when I move 2 into the correct place, I might move it past 1, which would mess up the position of 1. I am not really sure this is a good idea, since I'm not sure where the "correct place" of an element is, since any place around the circle could be correct.

Another idea I have is to fix 1 and sort the circle around 1 (i.e. I move 2 into place relative to 1, then 3 and so on). Then do it for 2 and so on, then take the minimum of the number of swaps I did while fixing each element. But is it true that this gives the optimal sequence of swaps?

This doesn't seem like an efficient solution either, since I am actually doing swaps on a list rather than some clever calculation. I know that the number of swaps in e.g. bubble sort is the number of inversions in the list. Is there a similar calculation I can do for circular lists?

Answer 1

Suppose we have two lists $L$ and $M$ of length $n$. They are identified as circular lists if and only if, when you write out $(L_1 \ldots L_n)$ and $(M_1 \ldots M_n)$, they give the same permutation, when considered as an element of $S_n$.

We can consider the graph $\Gamma$ with vertex set $(123\ldots n)^{S_n}$ (that is, the $n$-cycles in $S_n$). $\Gamma$ has an edge $(v, w)$ iff there is a transposition of adjacent elements (adjacent when we write $v$ down as $(v_1, \ldots, v_n)$) taking $v$ to $w$. This is well-defined since the only different way to write a cycle is by cyclically permuting it - the adjacent elements stay adjacent.

Given a circular list $L$, the problem is now finding the distance in $\Gamma$ from $L$ to $(1\ldots n)$.

To actually compute this, I used the GAP algebra system. We can take some steps to define the edges in a nicer way.

Let $G = S_n$. $G$ acts on the vertex set $V$:

$$\sigma \cdot (v_k)_{k=1}^n = (v_{\sigma(k)})_{k=1}^n$$

Also notice there is one vertex orbit, since any vertex can be relabelled to any other vertex.

Using this, we can define the group action in GAP:

G := SymmetricGroup(n);
ncycle := PermList(Concatenation([2..n], [1]));
all_ncycles := ncycle^G;
action := function(cycle, g)
    list := WritePermAsList(cycle);
    result := [1..n];
    for i in [1..n] do
        result[i] := list[i^g];
    od;
    return WriteListAsPerm(result);
end;

where WritePermAsList just writes e.g. the permutation (1,2) as the list [1,2] and so on.

Now we have the action, we can define a graph Gamma with vertex set $V$ with NullGraph and use AddEdgeOrbit to add all edges corresponding to the permutations we want to allow. In this case, we want to allow permutations of the form $(i\;i+1)$ and $(1 \; n)$. So we do AddEdgeOrbit(Gamma, [1, 1^Permutation(sigma, ncycles, action)]) for each sigma we want to allow.

Now computing the answer to the question I asked: "What is the minimal number of swaps required [to sort $L$]?" is just Distance(Gamma, 1, i) where i is the vertex representing our circular list $L$ since 1 represents $(1\ldots n)$ in our graph and we want to sort meaning get to $(1\ldots n)$.

I think this method isn't even that bad since I only really need this for small (length less than 10) lists. The simple structure of the graph means that we don't actually need to store all that much information about it (certainly we don't need to keep a huge list of vertices and edges in memory).

There are probably more insights about how to reduce this problem to something else, but this was good enough for me.

Answer 2

Even if you want to sort circularly, you definitely need a point of reference. Deciding where it should be implies you'll need to look around. If you don't want to look at every position, you can try skipping the pre-sorted intervals and sort the blocks rather than the individual elements. Notice this doesn't remove the circularity problem, it just reduces input size.

To be honest, looking at this problem gets me more tempted to show that as long as you have an answer with exactly one inversion, then you point of reference does not matter, than trying to show there is an optimal point to choose.