この記事は ひとりアドベントカレンダーRosettaCodeで楽しむプログラミング Advent Calendar 2025の14日めの記事です。
前回の続き。
もうこうなったら Bounds for Sorting by Prefix Reversal, W.H.Gates, C.H.Papadimitriou, Discrete Mathematics 27 (1979) 47-57. のアルゴリズムAを実装するしかない。
論文を読んでいく。
用語の定義など
対象として1からnの順列を考える。全体を $S_n$ と呼ぶ。
$\pi,\sigma$ あたりを変数として使う。$e_n = 12\cdots n$
順列に限定しない数字列は $x,y,b$ あたりの変数を使う。
順列 $\pi \in S_n$ に対して、$\pi(j)$ は $\pi$ の $1 \leq j \leq n$ 番めの数。
$|\pi(j) - \pi(j+1)| = 1$ のとき「対 $(j,j+1)$ は $\pi$ 中で adjacency (隣接) という。
$\pi = xby$ で、$b$ の内部が全て隣接であり、そのような区間として $b$ はこれ以上広げられないようなもののとき、$b$ を block (ブロック) という。
（補足：値に重複はないので、つまり上昇列か下降列かどちらかになる）
$\pi(j)$ がブロックに含まれないとき、つまり $(j-1,j),(j,j+1)$ のどちらも隣接でないとき、free (自由) であるという。
隣接の定義を拡張し、$\{\pi(j),\pi(j+1)\} = \{1,n\}$ のときもそうであるとする。（この辺りから怪しくなってくる。）
回転操作を繰り返して、順列が合計 $n-1$ 個の隣接を持つようにする。
ただし、n と 1 は隣接と考えることも勘定に入れての話。
実際の順列が [1 ～ n] なら整列は完了、[n ～ 1] ならもう一回全体を回せば完了、nと1が並ぶ場合は図1(a)か(b)の形である。このとき図1のように2手または3手で完全にソートできる。
図1
[k-1 ～ 1] [n ～ k] (a)
------------------+ 回転させる範囲を横線で示す
[k ～ n] [1 ～ k-1] (b)
--------+
[n ～ k] [1 ～k-1]
------------------+
[k-1 ～ 1] [k ～ n]
----------+
[1 ～ k-1] [k ～ n] 完成
以下、$o$ とは $\{-1,1\}$ のいずれかを当てはめる。値の加算はモジュロ$n$で考える。
（補足：これは $n + 1 = 1$ という、ヘンテコなモジュロである。値だけで、位置には適用しない。）
アルゴリズムA
入力：順列 $\pi \in S_n$
出力：$n-1$個の隣接を持つ順列 $\sigma$
（補足：πとの関係を言わないなら、ただそれを出せばいいので説明になっていない。）
変数：
- $\sigma$ 操作途中の順列
手続き：
初期設定：
$\sigma = \pi$ とする
本体：以下を繰り返す。
$t$ を $\sigma$ の先頭要素とする。
（補足：ここで$\sigma = t\sigma'$ と書いているが、$\sigma'$ は順列でないので変数カテゴリが違う。）
以下の8通りの場合分けで対応する計算を行う。（場合分けは一意ではない。）
（補足：複数の場合に適合する$\sigma$もありうる、と言っているのだが、そのときどうするとは言っていない。）
場合1:
$t,t+o$ が自由のとき。図2(a)の操作を行う。
$t+1$, $t-1$ が $\sigma$ のどこかに存在するが、それが自由状態であるとき、
隣り合わせで隣接を形成するように回転させる。
両方とも自由なときは手前と奥とどっちにするべきなのかは書いてない。
図2(a)
[t] -> [t+o] … [t+o] は自由
------+
<- [t]=[t+o] … 隣接した
計算としては、$\sigma$を前から順に調べて、$t+1$または$t-1$が見つかったとき、
その前後がともに差2以上の要素なら、この場合に適合するということだろう。
場合2:
$t$ が自由、$t+o$ がブロックの先頭であるとき、図2(b)の操作を行う。
場合1と分ける必要があったのだろうか。$t+o$から始まるブロックに$t$を前に隣接させて成長させる。
図2(b)
[t] -> [t+o ～]… [t+o] はブロックの先頭
------+
<- [t]=[t+o ～]… 隣接した
場合3:
$t$ が自由、$t+1$と$t-1$がどちらもブロックの右端(last element)であるとき、図2(c)の操作を行う。
図2(c)
[t] -> [～ t+o] => [～ t-o] … t+o,t-oがどちらもブロック右端
---------------+
[t+o ～] <- [t] => [～ t-o] …
-----------+
-> [～ t+o]=[t] => [～ t-o] … 隣接した
---------------------------+
[t-o ～] <= [t]=[t+o ～] <- …
-----------+
=> [～ t-o]=[t]=[t+o ～] <- … さらに隣接した
つまり、「先頭要素の隣接要素が単独だろうがブロックだろうが、それを極力成長させるように操作する」という方針か。
上の図では、3回目の大回転の前後で t の位置が偶然変化していないが、実際には変わる。
最後の回転の長さは t+o と t-o の位置の差となる。
場合4:
$t$はブロックにあり、$t+o$は自由のとき、図2(d)の操作を行う。
図2(d)
[t ～] -> [t+o] …
---------+
<- [～ t]=[t+o] …
図2(a)と違いが少なすぎて気づかなかった。場合1でtが自由だろうがブロックにあろうがやることは同じ、ということ。
場合5:
tはブロックにあり、$t+o$はブロックの先頭のとき、図2(e)の操作を行う。
図2(e)
[t ～] -> [t+o ～] …
---------+
<- [～ t]=[t+o ～] …
場合4は少し先走っていた。場合1と場合2がまとめて扱えたように、場合4と場合5はまとめて扱える。
そして、場合1+2と、場合4+5はまとめて扱える、ということ。
場合6:
tがブロックにある。位置 $k+1$ にあるその右端を $t+ko$ $(k > 0)$ とする。
このブロックのt側の隣接値 $t-o$ は別のブロックの終端にあり、k側の隣接値 $t+(k+1)o$ は自由のとき、両者の位置関係によって、図2(f)または(g)を行う。
考察：
（両側に）自由という概念を導入したのはミスで、片側が隣接していない、そこを切り離しても問題ない、ということだけが関心事なので、そうするべきだった気がする。
また、ブロックはその中を切ってはいけない連続、というだけのことなので、長さ1でもブロックとみなせば、特にtが自由かどうかは初めから重要ではなかった。
図の t+k1o は $ t + (k+1)o$ の意味。
図2(f)
[t ～ t+ko] -> [t+k1o] => [～ t-o] … 次の値が手前にあるとき
----------------------+
[t+k1o] <- [t+ko ～ t] => [～ t-o] …
----------+
-> [t+k1o]=[t+ko ～ t] => [～ t-o] … 隣接した
----------------------------------+
[t-o ～] <= [t ～ t+ko]=[t+k1o] <- …
-----------+
=> [～ t-o]=[t ～ t+ko]=[t+k1o] <- … 反対側も連結された
図2(g)
[t ～ t+ko] -> [～ t-o] => [t+k1o] … ブロックが手前にあるとき
----------------------------------+
[t+k1o] <= [t-o ～] <- [t+ko ～ t] …
----------------------+
-> [～ t-o] => [t+k1o]=[t+ko ～ t] … 連結した
----------------------------------+
[t ～ t+ko]=[t+k1o] <= [t-o ～] <- …
----------------------+
=> [t+k1o] [t+ko ～ t]=[t-o ～] <- … 連結した
場合7:
tがブロックにある。位置 $k+1$ にあるその右端を $t+ko$ $(k > 0)$ とする。
このブロックのt側の隣接値 $t-o$ は別のブロックの終端にあり、k側の隣接値 $t+(k+1)o$ も別のブロックの端にあるとき、
k側の隣接値がブロックのどちらの端かによって、図2(h)または(k)を行う。
今回は $t-o$ 側のブロックは関係してこない。
図2(h)
[t ～ t+ko] -> [t+k1o ～] … 次の値が左端にあるとき
-----------+
[t+ko ～ t] -> [t+k1o ～] …
--------------+
<- [t ～ t+ko]=[t+k1o ～] …
図2(k)
[t ～ t+ko] -> [～ t+k1o] … 次の値が右端にあるとき
-------------------------+
[t+k1o ～] <- [t+ko ～ t] …
-------------+
-> [～ t+k1o]=[t+ko ～ t] …
場合8:
いずれでもないとき、整列は完了しているので終わる。
これで場合が尽くせていることを確認するのがまず大変、見通しが悪い。
考察
結局、先頭要素が左端となる（長さ1も含めた）ブロック [t ～ t+ko] と、その両端の次の値 t-o t+k1o は、t側はブロックで連続しているからその反対側だけがブロックをなす可能性があって、[t-o ～] もしくは [～ t-o] と [t+k1o ～] もしくは [～ t+k1o] がそれぞれどこかにある。
位置関係によって、良い感じにこれらのブロックを繋ぐような操作手順を漏れなく列挙したという事か。
（そういうものが存在しないときは、tから始まるブロックが全体を覆っているか、片方だけしかない、図1の状況にあるから、後始末して終わりになる。）
先頭要素を含むブロックと、それに隣接するブロックとのいずれかと連結させる。
ブロックになったら二度とそこは千切らない、という方針がこのアルゴリズムの肝のようなので、その視点で分析してみる。
3つのブロックの向きと位置関係を列挙するとこうなる。アルゴリズムAで適合する場合も添える。
[t ～ t+ko] -> [t+k1o ～] => [t-o ～] … 右と(e)(d)(b)(a)
[t ～ t+ko] -> [～ t+k1o] => [t-o ～] … 右と(e)(d)(b)(a)
[t ～ t+ko] -> [t-o ～] => [t+k1o ～] … 中と(e)(d)(b)(a)
[t ～ t+ko] -> [t-o ～] => [～ t+k1o] … 中と(e)(d)(b)(a)
[t ～ t+ko] -> [t+k1o ～] => [～ t-o] … 中と(h)
[t ～ t+ko] -> [～ t+k1o] => [～ t-o] … 中と(k) 全体で(f)
[t ～ t+ko] -> [～ t-o] => [t+k1o ～] … 右と(h)
[t ～ t+ko] -> [～ t-o] => [～ t+k1o] … 右と(k) 全体で(g)
(a)(b)(d)(e) は、1手で一つ隣接が増える、一番お得な操作。しかし片方だけしか扱わない。
(h)(k) は2手で一つ隣接が増える。片方だけ。
(f)(g) は (k) の特殊な場合で、t+k1oが自由と条件付けられているが、実際には右に自由なら適用できる。（下図(f'),(g')）
(k)が冗長というか、(f)(g)の前半は(k)そのものである。逆に (f)(g) の後半はまた別の機会にできる。
(f')
[t ～ t+ko] -> [～ t+k1o] => [～ t-o] …
-------------------------+
[t+k1o ～] <- [t+ko ～ t] => [～ t-o] …
-------------+
-> [～ t+k1o]=[t+ko ～ t] => [～ t-o] …
-------------------------------------+
[t-o ～] <= [t ～ t+ko]=[t+k1o ～] <- …
-----------+
=> [～ t-o]=[t ～ t+ko]=[t+(k+1)o] <- …
(g')
[t ～ t+ko] -> [～ t-o] => [～ t+k1o] …
-------------------------------------+
[t+k1o ～] <= [t-o ～] <- [t+ko ～ t] …
-------------------------+
-> [～ t-o] => [～ t+k1o]=[t+ko ～ t] …
-------------------------------------+
[t ～ t+ko]=[t+k1o ～] <= [t-o ～] <- …
-------------------------+
=> [～ t+k1o] [t+ko ～ t]=[t-o ～] <- …
と、この後実装を色々と試みたのだが、論文ではあいまいになっている細かいところから色々とほころびが生じて、完全な実装は無理と断念した。
例えば 2 1 という列は、普通に考えれば下降列で、一度の反転で整列が完了する。
しかし、1とnが繋がっているルールにより 2 + 1 = 1 (mod 1) として上昇列だとも解釈できてしまう。
すると、modでラウンドアップしている上昇列、図1(a)の下 [k ～ n][1 ～ k-1] の変換規則が適用され、3手かかってしまう。
「その場その場で最も都合良く解釈する」はつらい。
アルゴリズムAm
「一度作ったブロックは壊さず、少ない手数で隣接を広げる」という精神を引き継いで、少し単純化した版のアルゴリズムを考える。
nから1へのラウンドアップは行わない。
列は要素の列ではなく、上昇列、下降列、長さ1、の3種類のブロックの列という形で扱う。
二つのブロックが並んだとき、連結できるなら連結して結果を返す関数を基本演算として付ける。
また、一つのブロックを反転させる操作も付ける。
data Block = S Int | I Int Int | D Int Int -- singleton/increasing/decreasing
deriving Show
connect :: Block -> Block -> [Block]
connect (S x) (S y) | succ x == y = [I x y]
| pred x == y = [D x y]
connect (S x) (I y z) | succ x == y = [I x z]
connect (S x) (D y z) | pred x == y = [D x z]
connect (I x y) (S z) | succ y == z = [I x z]
connect (D x y) (S z) | pred y == z = [D x z]
connect (I x y) (I z w) | succ y == z = [I x w]
connect (D x y) (D z w) | pred y == z = [D x w]
connect p q = [p, q]
flipBlock :: Block -> Block
flipBlock (I x y) = D y x
flipBlock (D x y) = I y x
flipBlock s = s
入力は普通に順列なリストとする。
なのでまず [Block] に変換する。
pairwise :: [Int] -> [Block]
pairwise = foldr step []
where
step x (p:ps) = connect (S x) p ++ ps
step x [] = [S x]
ブロック列と回転のサイズ（ブロック単位）を引数にとり、回転させ、可能ならブロックの連結を行って返す下請け関数：
flipBlocks :: [Block] -> Int -> [Block]
flipBlocks xs i =
case splitAt i xs of
(a:as1,b:bs1) -> reverse (map flipBlock as1) ++ connect (flipBlock a) b ++ bs1
(as,bs) -> reverse (map flipBlock as) ++ bs
ここから本体。
先頭のブロックと、それに接続しうる3つのブロックの位置関係と向きにより、回転を行う。
[t ～ t+ko] -> [t-o ～] 図2(e)(d)(b)(a)相当 モードEとする
[t ～ t+ko] -> [t+k1o ～] 図2(h)相当 モードHとする
[t ～ t+ko] -> [～ t+k1o] 図2(k)相当 モードKとする
[t ～ t+ko] -> [～ t-o] 図2(f)の後半相当 モードXとする
[t] -> [～ t-o] モードXの k = 0 のとき 図2(c)の片側相当 モードxとする
モードE,H,KはアルゴリズムAと同じ回転でよい。
モードXは次のようにする。モードxは最初の先頭ブロック反転を行わない。
[t ～] -> [～ t-o] …
------+
[～ t] -> [～ t-o] …
------------------+
[t-o ～] <- [t ～] …
-----------+
-> [～ t-o]=[t ～]
手数に対する連結箇所の獲得比率が、モードEは1:1、モードH,Kは2:1、アルゴリズムAではこれが上限なのに対して、モードXを使うアルゴリズムAmは3:1と悪化している。
これを様々な場合分けで極力比率を高めた結果が図2という訳で、元論文は相当考えた結果だとようやく実感できた。
ループごとにこの5通りに場合分けをしてブロックの列を短くするメインループを作る。
algorithmAm :: [Int] -> [[Block]]
algorithmAm xs0 = loop $ pairwise xs0
where
loop tts@(t:ts) = tts :
case t of
_ | Just i <- posE -> loop (flipBlocks tts i)
| Just i <- posH -> let ts1 = flipBlock t : ts in ts1 : loop (flipBlocks ts1 i)
| Just i <- posK -> let ts1 = flipBlocks tts (succ i) in ts1 : loop (flipBlocks ts1 i)
S _ | Just i <- posX -> let ts1 = flipBlocks tts (succ i) in ts1 : loop (flipBlocks ts1 i)
_ | Just i <- posX ->
let ts0 = flipBlock t : ts
ts1 = flipBlocks ts0 (succ i)
in ts0 : ts1 : loop (flipBlocks ts1 i)
_ -> post tts
where
posE = succ <$> findIndex (connectable $ flipBlock t) ts
posH = succ <$> findIndex (connectable t) ts
posK = succ <$> findIndex (flip connectable $ flipBlock t) ts
posX = succ <$> findIndex (flip connectable t) ts
connectable p q =
case connect p q of
[_] -> True
_ -> False
5つのパターンに当てはまらない列は、図1相当の終了処理でソート完了となる。
これがまた大変に泥臭くなってしまった。
n = length xs0
doPost ts = ts : post ts
post [I a b] | a == 1, b == n = []
| b == 1 = [[D n 1],[I 1 n]]
| a == n = [[D b 1, S n],[I 1 n]]
| otherwise = post [I a n, I 1 b]
post [D a b] | a == n, b == 1 = [[I 1 n]]
| b == n = [[I 1 n]]
| a == 1 = [[I 2 n, S 1],[D n 1],[I 1 n]]
| otherwise = post [D a 1, D n b]
post [D a b, D c d] | b == 1, c == n = doPost [I d c, I b a]
post [I a b, I c d] | b == n, c == 1 = doPost [D b a, I c d]
post [D a b, I c d] | a == n, c == 1 = doPost [D d c, I b a]
post [D _ b, I _ d] | b == 1, d == n = [[I 1 n]]
ghci> algorithmAm [1,3,4,2,5]
[[S 1,I 3 4,S 2,S 5],[D 4 3,I 1 2,S 5],[D 2 1,I 3 5],[I 1 5]]
ghci> algorithmAm [1,2,3,5,4]
[[I 1 3,D 5 4],[I 4 5,D 3 1],[D 5 1],[I 1 5]]
ghci> algorithmAm [6,7,2,1,8,9,5,3,4]
[[I 6 7,D 2 1,I 8 9,S 5,I 3 4],[D 9 8,I 1 2,D 7 5,I 3 4],[I 8 9,I 1 2,D 7 5,I 3 4]
,[D 2 1,D 9 5,I 3 4],[I 5 9,I 1 4],[D 9 5,I 1 4],[D 4 1,I 5 9],[I 1 9]]
ghci> algorithmAm [7,6,9,2,4,8,1,3,5]
[[D 7 6,S 9,S 2,S 4,S 8,S 1,S 3,S 5],[S 4,S 2,S 9,I 6 8,S 1,S 3,S 5],[S 1,D 8 6,S 9,S 2,D 4 3,S 5]
,[S 9,I 6 8,I 1 2,D 4 3,S 5],[D 8 6,S 9,I 1 2,D 4 3,S 5],[I 6 9,I 1 2,D 4 3,S 5],[I 3 4,D 2 1,D 9 5]
,[D 4 1,D 9 5],[I 1 4,D 9 5],[I 5 9,D 4 1],[D 9 1],[I 1 9]]
ghci> map (testStrategy1 algorithmAm) [2 .. 9]
[(0,0),(0,0),(4,4),(41,53),(348,513),(3036,5020),(28211,51713),(281197,569403)]
ghci> map (sum . IM.elems . (madeMaps !!)) [4 .. 9]
[60,425,3295,28280,267711,2780947]
性能評価
全ての順列に対して、手数が最適でない順列の個数を数えてみた。
| N | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|
| 母数 $N!$ | 24 | 120 | 720 | 5040 | 40320 | 362880 |
| 素朴 | 4 | 45 | 423 | 3771 | 34587 | 335658 |
| Java | 2 | 25 | 278 | 2847 | 28924 | 301170 |
| Am | 4 | 41 | 348 | 3036 | 28211 | 281197 |
最適な手順よりも増えている、追加ステップ数合計を数えてみた。
（母数とは最適な手順の手数の合計）
| N | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|
| 母数 | 60 | 425 | 3295 | 28280 | 267711 | 2780947 |
| 素朴 | 6 | 73 | 773 | 8116 | 88977 | 1034045 |
| Java | 2 | 29 | 377 | 4540 | 54765 | 681653 |
| Am | 4 | 53 | 513 | 5020 | 51713 | 569403 |
考察
Nが小さい範囲では、素朴な手法を改善したJava版のアルゴリズムに後れを取っている。
Nが大きくなってくると、かなりの性能を示すようになるが、それでも最適な手順に比べるとまだ開きがある。
本物のアルゴリズムAを実現できなかったのは残念だが、一定の成果は得られたのではないだろうか。
高次元のHaskellerだと、loop や post のバタ臭い記述をもっとスマートに書けたりするのかな。