3
$\begingroup$

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]
$\endgroup$
  • $\begingroup$ But what's your question? $\endgroup$ – David Richerby Feb 12 '15 at 23:11
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks! And sorry for having missed the references in the Wikipedia article, which arguably should define sorting by reversals and move it from the History to the Variations section. I'll suggest this in the talk page of the article. $\endgroup$ – Aristide Feb 12 '15 at 14:15
  • $\begingroup$ @Aristide No problem. Likewise I missed the explicit statement that finding the sorting distance is hard for the unsigned case. Odd I could find no separate page for the full reversal sorting on Wikipedia, but then we are not allowed to complain, as we are free to start the page ourselves. $\endgroup$ – Hendrik Jan Feb 13 '15 at 13:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.