4
$\begingroup$

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,

  • 0
    @mjqxxxx: Thanks for your explanation. That's exactly my situation.2011-03-08

2 Answers 2

2

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.

  • 0
    @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.2011-03-08
1

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.

  • 0
    I see, sorry. I was thinking in terms of pairwise swaps, my bad.2011-03-07