Optimal way to sort a list by reversing sublists

Question

Now I recently saw this question (can't exactly remember where) about how few operations were needed to sort a list of numbers by exclusively reversing sublists.

Here is an example:
Unsorted Input: 3, 1, 2, 5, 4

One of the possible answers is:
1. Reverse index 0 through 3, giving 5, 2, 1, 3, 4
2. Reverse index 0 through 4, giving 4, 3, 1, 2, 5
3. Reverse index 0 through 3, giving 2, 1, 3, 4, 5
4. Reverse index 0 through 1, giving 1, 2, 3, 4, 5

However, after trying my hand at this problem it proved quite difficult for someone not experienced in algorithms to actually create a piece of code that finds the best solution. The answer noted above was simply done by brute-forcing all possible combinations, but this becomes unbearably slow when lists are longer than 10 numbers (10 takes <2s, 14 took more than 10 minutes). Refitting any existing sorting algorithms doesn't work either because they were built to only swap single elements at a time (and swapping 2 numbers by reversing sublists will take 1-2 operations which is not optimal at all). I have also tried sorting networks because the max size is already determined before running the program, but I didn't have much luck with them either (they also rely on swapping, which is inefficient when you have the ability to swap multiple at a time). I also tried to make a function that would "optimize" a list of operations, as an attempt to make existing sorting algorithms viable, but those answers were also far longer than the optimal ones (think of 16 vs 6).

So, after spending quite some time on this, I simply cannot find a better way to find the shortest solution short of brute-forcing it. As I am a student, I do not have much experience in the art of sorting, algorithms and other math "magic", but I was wondering if anyone here might have a try. The best answer of course is simply giving a hint, because I wouldn't mind trying to solve it with some hints of the smarter minds floating around StackOverflow.

Lets say that all numbers are unique and in the range 0 - 100 (both exclusive). The length of the array is something like 3 < N < 15, because I seem to recall that the original question does not use big arrays either.

Answer 1

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.