Okay, here's my quick solution with A\* : http://cs.stanford.edu/~fra[REMOVE THI...

Okay, here's my quick solution with A* : http://cs.stanford.edu/~fra[REMOVE THIS]nkel/listsort.py

Pass Astar a sequence and the reversal length. I'm a total Python noob so I may have done something stupid and/or inelegant (in which case please tell me so that I learn :) ).

Example:

  >>> result = Astar([1, 4, 2, 3, 6, 5], 2)
  >>> result.path
  [[1, 4, 2, 3, 6, 5], [1, 2, 4, 3, 6, 5], [1, 2, 3, 4, 6, 5], [1, 2, 3, 4, 5, 6]]

result will just be -1 if there was no path.