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?