title: Generalisation of pancake sorting with arbitrary flipped slices?
body: <p>In <a href="http://en.wikipedia.org/wiki/Pancake_sorting" rel="nofollow">pancake sort</a>, the primary operation is: flip all pancakes <strong>above</strong> a given position. What about flipping all pancakes <strong>between</strong> two given positions? Anybody knows if this has been studied?</p>
  
  <p>To illustrate the problem, here is a quick brute-force, greedy implementation in Python 2.7 (not quite sure it always converges though):</p>
  
  <pre><code>def sort(a):
      entropy = 0
      for i in range(len(a) - 1):
          entropy += abs(a[i] - a[i+1])
      while True:
          max_improvement = 0
          for i in range(len(a) - 1):
              for j in range(i + 1, len(a)):
                  improvement = 0
                  if i &gt; 0:
                      improvement += abs(a[i] - a[i-1]) - abs(a[j] - a[i-1])
                  if j &lt; len(a) - 1:
                      improvement += abs(a[j] - a[j+1]) - abs(a[i] - a[j+1])
                  if improvement &gt; max_improvement:
                      max_improvement = improvement
                      (next_i, next_j) = (i, j)
          if max_improvement == 0:
              if a and a[0] &gt; a[-1]:
                  a[:] = a[::-1]
                  print a
              return
          entropy -= max_improvement
          a[next_i:next_j+1] = a[next_i:next_j+1][::-1]
          print a
  
  a = [7, 1, 3, 8, 6, 0, 4, 9, 2, 5]
  print a
  sort(a)
  </code></pre>
  
  <p>Output:</p>
  
  <pre><code>[7, 1, 3, 8, 6, 0, 4, 9, 2, 5]
  [7, 6, 8, 3, 1, 0, 4, 9, 2, 5]
  [7, 6, 8, 9, 4, 0, 1, 3, 2, 5]
  [7, 6, 8, 9, 4, 5, 2, 3, 1, 0]
  [9, 8, 6, 7, 4, 5, 2, 3, 1, 0]
  [9, 8, 7, 6, 4, 5, 2, 3, 1, 0]
  [9, 8, 7, 6, 5, 4, 2, 3, 1, 0]
  [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
  </code></pre>