Cheap and Secure Web Hosting Provider : See Now

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

, , No Comments
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] 
Asked By : Aristide

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.

Best Answer from StackOverflow

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

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback