Optimal way to sort a list by reversing sublists

Nothing optimal but an idea to use in some similar cases.

An idea would be using recursion and keeping the "best" score encountered previously in order to avoid exploring further useless combinations.

A first limit is obviously n-1 for a list of length n: no "path" should be longer than n-1 since a trivial solution exist with score n-1.

Then let a sorting function call itself several times with parameters being:

• current state of the list
• length of the path to the current state (1, then 2, then 3, ...)
• some list of tuples being a description of the path to the current state
• best score found (initially n-1)
• description of the best solution found (list)

Each time the function is called (by itself) it can perform about n² operations and call itself again by adding 1 to the length of the path (and of course fixing other parameters as well) but only if this incremented length remains lower than the best score.

Since using recursion will be more or less similar to exploring a tree, you will avoid exploring some branches if you are lucky enough to find "good" solutions soon enough.

It should work for sizes 3 < N < 15 but you can surely find better.

I've found a solution with a smaller number of swaps for your example:

1. reverse indexes 0 to 2: 2 1 3 5 4
2. reverse indexes 0 and 1: 1 2 3 5 4
3. reverse indexes 3 and 4: 1 2 3 4 5

Seems like what @greybeard suggested is the best approach. Maybe even think of a sort of heuristics based on greedy+optimization functions based on some notion of "cost".

Maybe for example for each element you can calculate "how far" it is from its original index in a sorted list and start by reversing the highest cost list first (as to minimize subsequent swaps, hopefully) until everything is sorted.

Of course, haven't really tested it, but, as a start, it might help you.

Best,Bruno

Here's an idea that use a greedy approach (not proven to be optimal). The idea is in each step look for the reversion that maximally increases the order. Let's define the order of a list as the length of the longest ordered parts in that list, and let's say that a part of the list is ordered if it is sorted either forwards or backwards.

E.g. the list [3 4 5 1 2] has two ordered parts: [3 4 5] and [1 2]. The best move from this state would take the first 4 elements an revert them. The result is the list [1 5 4 3 2]. The order of the new list is increased because now the maximal ordered subsequence is 4 elements long (it it the subsequence [5 4 3 2]).

If no moves that increase the order of the list are is possible, then prefer a move that sorts (a part of) the list in the right order. (Also use this for breaking ties.)

On the example above this strategy works like this:

[3 1 2 5 4] (order 2) -> [3 4 5 2 1] (order 3) -> [5 4 3 2 1] (order 5) -> [1 2 3 4 5] (order 5, sorted properly).

which leads to the result in shorter time than the OP's sequence of moves. The complexity of this algorithm is O(n^3) or better, as each step requires comparing all O(n^2) possible moves.

The point where this breaks down is when there are multiple moves that give the same order. For example, if "6" is added to the end of the original example, there is a move that leads to order 4 trough the sequence [4 5 6], but that move is a suboptimal choice. A possible idea how to fix this is to do not consider elements that are in their already-sorted places on both ends of the list when calculating the score. It's clear that there's never a reason to touch those elements, so the algorithm should only consider the middle, yet-unsorted part of the list.