This problem asks:

Given: Two permutations π and γ, each of length 10.

Return: The reversal distance drev(π,γ), followed by a collection of reversals sorting π into γ.

References

  1. Reversal sorting
  2. Reread Euna Park’s Master’s Project
  3. Reread A popularization of Park’s thesis
  4. Dan Halligan’s solution

Restating the problem

I will get two permutations of the integers from 1 to 10 inclusive. I need to return the minimum number of subset reversals required to transform the first permutation into the second. Then I need to return the list of indexes that define subset that needs to be reversed in each step to accomplish the transformation.

Solution steps

I solved the first part of the problem already in Reversal Distance.

I started by copying my code from here, then I made a few changes to fit the code to this challenge.

My previous code worked to return the minimum number of reversals required. Next, I need to keep track of which indexes get reversed to accomplish that optimal transformation.

I invested 20 hours in trying to modify my existing code so that it would keep track of what indexes need to be reversed at each step to perform the transformation in the least number of steps. At the end, I hadn’t made any measurable progress.

I looked at Dan Halligan’s solution to this challenge for ideas, then followed his approach in my own implementation.

Post-solution notes

Challenges solved so far: 63

How many people solved this before me: 926

Most recent solve before me: three weeks ago

Time spent on challenge: 25 hours

Most time-consuming facet: revising functions to store and pass history

Solutions from others: There were many different successful approaches to saving reversal history.

Closing thoughts: I didn’t have a single original thought that moved me forward in solving this challenge. Every helpful idea came from reading code from others. I’ve put an entry in my calendar for six months from now, March 7, 2026, to come back and try to solve this challenge from scratch by myself.