パンケーキ ソートの主な操作は、指定された位置より上のすべてのパンケーキを裏返すことです。与えられた 2 つの位置の間ですべてのパンケーキをひっくり返すのはどうですか? これが研究されているかどうか知っている人はいますか？
問題を説明するために、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]