# Find the fewest moves to sort a list

This is a programming problem that I'm trying to solve at TopCoder arena. However, I feel like it need Mathematics to prove its correctness.

Problem
Given a list $L$ of $n$ elements, and a number $k, k \leq n$, where $k$ defined as a number consecutive elements can be reversed. For example: $L = \{ 4, 3, 2, 1 \}$ and $k = 3$

reverse at $0$ yield a new list $L = \{ 2, 3, 4, 1 \}$

So our goal is to sort the list in ascending order by reversing $k$ element each time if possible.

My question is, what condition must be hold in order to have an impossible case? And how to find the fewest moves in term of $n$ and $k$? Here are few examples:

{1,2,3}
3
Fewest move is 0

{3,2,1}
3
Fewest move is 1

{5,4,3,2,1}
2
Fewest move is 10

{3,2,4,1,5}
4
This is impossible case


Thanks,

-
Is the number of times where you reverse a sublist unbound, as well as the position of the sublist? With $k=2$ you would have bubble sort, correct? This would always work for all $n \geq 2$. Are you looking for $n$ and $k$ that don't work? – Christian Lindig Mar 4 '11 at 18:59
@Christian Lindig: Yes if k=2, that is bubble sort. I think $n$ should not be involved, since the condition was $k \leq n$. So I guess the only thing matters is k, andI'm looking for condition of $k$. Thank you. – Chan Mar 4 '11 at 19:30
I'm relatively new to this site, so I don't know what the rules are with respect to this sort of thing; but I would have thought that asking for solutions to competition problems on other sites is not in the spirit of this site? Basically the OP is asking to use our collective abilities to increase her or his personal rating at TopCoder. I'd appreciate if someone more versed in the etiquette of this site than myself would comment on whether they find that appropriate. – joriki Mar 7 '11 at 8:02
Use heaps! Construct them. See corman and Leiserson etc "Introduction to algorithms". – Dilawar Mar 7 '11 at 8:54
@joriki @Raphael @Didier: TopCoder has old problems that members can study and test at their leisure, with no rating change, in so-called practice arenas. This is presumably one of those. Moreover, the algorithm competitions are only an hour long; so even if it was unethical for OP to ask this question a few days ago, it is certainly okay for us to try to answer it now :). – mjqxxxx Mar 7 '11 at 19:42

If the length of each reversal you can use is exactly $k$, and not at most $k$, then as far as I know the computational complexity of the problem is open. However, it has been investigated by Chen and Skiena in the case of permutations, in their paper entitled "Sorting with fixed-length reversals", where they give among other results conditions on the feasibility of the sorting problems with respect to $k$.

Update: here is a free version for those who do not have access to the above.

-
From the abstract, their problem seems slightly different, since they use a turnstile (i.e., periodic boundary conditions on the list). – mjqxxxx Mar 4 '11 at 19:59
Thanks for your reply. However, this problem is only 250 points, i.e level 1, so I think there must be an easier trick to find out the condition of $k$. – Chan Mar 5 '11 at 4:59
@mjqxxxx: They actually treat both circular and ordinary permutations in that paper. – mhum Mar 8 '11 at 6:00
@Chan: Given that the keywords for this problem on TopCoder are "Graph Theory, Simple Search, Iteration, Sorting", it seems unlikely that they were looking for some closed-form, mathematical solution. It seems far more likely that they were looking for participants to code a simple breadth-first search. – mhum Mar 8 '11 at 6:03

Edit: This is only a helpful hint if you consider the minimum amount of swaps needed to sort a sequence.

Just two hints:

• Permutations are uniquely given by their cyclic form, e.g. $2143$ is $(1,2)(3,4)$.
• If you have a cycle of $k$ elements, you need $k-1$ swaps to bring the elements to their positions in the sorted sequence

Work for you: proof optimality of this and implement a function that finds all circles in a given sequence.

-
If I understood the question correctly, he can only use reversals, not transpositions, so the disjoint cycle decomposition will only help him for $k\leq 3$. I thought Chan wanted an answer for all $k$, but I might be wrong. – Anthony Labarre Mar 7 '11 at 13:38
I see, sorry. I was thinking in terms of pairwise swaps, my bad. – Raphael Mar 7 '11 at 13:48