0

在煎饼排序中，主要操作是：将所有煎饼翻转到给定位置之上。在两个给定位置之间翻转所有煎饼怎么样？有人知道这个有没有研究过？

为了说明这个问题，这里有一个 Python 2.7 中的快速暴力、贪婪实现（虽然不太确定它是否总是收敛）：

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)

输出：

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

1 回答 1

0

根据评论者的建议，我在CS StackExchange Beta上交叉发布了这个问题，它很快就收到了我正在寻找的答案：这个问题称为反向排序。

这是一个有效的Python 实现。

注意：由于不能保证当前的 SE 站点将超过 beta，因此我想在这里保持我的问题开放，恕我直言，它同样是主题。如果它违反 StackExchange 礼仪，请随意关闭它。

于 2015-02-12T13:24:43.773 回答