3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ What are you looking for? Are you looking for an algorithm that, given a list, will compute the minimum number of swaps? Are you looking for an asymptotic upper bound on the number of swaps that holds for all lists? Do you already know what the solution is if you don't allow it to be sorted "circularly", and if so, can you edit the question to show us that solution? $\endgroup$ – D.W. Feb 10 at 19:31
  • $\begingroup$ Have you made any progress recently? $\endgroup$ – Apass.Jack Feb 13 at 22:35
  • $\begingroup$ Yes, I actually did solve this problem using a different approach. I found that my original method of manually trying to do the swaps was too hard to get right, so I did something a bit more clever involving defining a group action on the circular lists. Look at my answer below. You could also adapt my solution to restrict to arbitrary types of permutation, not just adjacent swaps. $\endgroup$ – pizzaroll 2 days ago
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Nice writeup. I would call this method the brute force search. Have you run the algorithm given a random list of size no less than 20? $\endgroup$ – Apass.Jack 2 days ago
-1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.