回答のページにようこそ.自分で答えを見つけることができましたか?

 

 問題は,順列 (1,2,4,3,6,5) をプレフィックス反転を6回だけつかってソートされた順列 (1,2,3,4,5,6) に変形することでした.

 

 この問題にはいくつかの解があって,たとえば次のような列

 

(1,2,4,3,6,5) à (3,4,2,1,6,5) à (4,3,2,1,6,5) à (5,6,1,2,3,4) à (6,5,1,2,3,4) à (4,3,2,1,5,6) à (1,2,3,4,5,6)

 

は解のひとつです(6回が手数の下界で,5回でソートすることはできません).実はこの順列は,ソートするのにもっとも多くのプレフィックス反転を必要とするような特別な順列から距離1離れた場所にあります.特別な順列というのは,(2,1,4,3,6,5) のように「降順にソートされた部分列が昇順に並んでいる」順列のことで,既知結果であるFischer2-近似アルゴリズムは,そのような特別な順列に注目することでつくられています.

 

ちなみにパンケーキソート問題については,ビル・ゲイツがハーバード大学在籍中にいくつかの結果を出しており,そのときの教授が,ビル・ゲイツとの共著で論文として発表しています(これが現在のところビル・ゲイツの唯一の学術論文だと聞いたことがあります)

 

トップページへ戻る