Cheap and Secure Web Hosting Provider : See Now

# [Answers] Generalisation of pancake sorting with arbitrary flipped slices?

, ,
Problem Detail:

In pancake sort, the primary operation is: flip all pancakes above a given position. What about flipping all pancakes between two given positions? Anybody knows if this has been studied?

To illustrate the problem, here is a quick brute-force, greedy implementation in Python 2.7 (not quite sure it always converges though):

``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 > 0:                     improvement += abs(a[i] - a[i-1]) - abs(a[j] - a[i-1])                 if j < len(a) - 1:                     improvement += abs(a[j] - a[j+1]) - abs(a[i] - a[j+1])                 if improvement > max_improvement:                     max_improvement = improvement                     (next_i, next_j) = (i, j)         if max_improvement == 0:             if a and a[0] > 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) ``

Output:

``[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] ``

#### Answered By : Hendrik Jan

Yes, it has been studied quite a lot. The general problem is called sorting by reversal. It is important as it is related to finding the similarity between genomes of two species that have the same genes, but in different order.

There are two variants of the problem, one where the orientation of the pancake [= gene] also matters. This is modelled using so-called signed permutations. See also the last paragraph and references in the Wikipedia page you quote.

There is a very precise characterization of the number of reversals needed for signed permutations in terms of the structure of a certain graph. For the unsigned variant, which you use in your question, the problems seems NP-hard (see the Wiki page) and even hard to appoximate.

Question Source : http://cs.stackexchange.com/questions/38286

3.2K people like this