順列をもれなく生成するアルゴリズムの一つSteinhaus–Johnson–Trotter algorithm (Wikipedia) (以下Johnson-Trotterアルゴリズム)に関して以下の３つを紹介します
- Johnson-Trotterアルゴリズム（オリジナル）
- Johnson-Trotterアルゴリズム（再帰的）
- 指定された順列が何番目に出てくるか
Johnson-Trotterアルゴリズム（オリジナル）
Wikipediaによれば教会の鐘をならす順番を常に違ったものにするために、隣の２つの鐘の順序だけを変えてゆくことから考え出されたとのことです。
そのアルゴリズムはJohnson Trotter Algorithm (youtube)に詳しく説明がありますが。簡単に言うと以下の処理を繰り返します。
\begin{align}
&1.\ \ \ 数を昇順に並べ上に左向きの矢印を書く&\\
&\begin{matrix}
&\leftarrow & \leftarrow & \leftarrow & \leftarrow \\
&1 & 2 & 3 & 4 \\
&\end{matrix} \\
&2.\ \ 一番大きい4の矢印の方向の数が4より小さければ入れ替える \\
&\begin{matrix}
&\leftarrow & \leftarrow & \color{red}{\leftarrow} & \color{red}{\leftarrow} &&\leftarrow & \leftarrow & \color{red}{\leftarrow} & \color{red}{\leftarrow}\\
&1 & 2 & \color{red} {3} & \color{red}{4} &\Rightarrow &1 & 2 & \color{red} {4} & \color{red}{3} \\
&\end{matrix} \\
&3. \ \ 4が入れ替えられなければ、次の3で同様のことをする。\\
&\ \ \ \ \ このとき4の上の矢印を逆にする\\
&\begin{matrix}
&\color{red}{\leftarrow} & \leftarrow & \color{red}{\leftarrow} & \color{red}{\leftarrow}&&\color{red}{\rightarrow} & \leftarrow & \color{red}{\leftarrow} & \color{red}{\leftarrow}\\
& 4 &1 & \color{red} {2} & \color{red}{3}&\Rightarrow & 4 &1 & \color{red} {3} & \color{red}{2} \\
&\end{matrix} \\
&4.\ \ \ 以下同様に入れ替えた数より大きい数の上の矢印を逆する
\end{align}
これをそのまま実装したのが以下のコードで、24通りの順列をもれなく生成することが出来ました。（後の説明のために出力をBlockに分けています）
import math
def johntrot(N):
perm = [[m, -1] for m in range(1,N+1)] # ((1,-1),(2,-1),...,(N,-1))
for _ in range(math.factorial(N)):
npart = [m for (m,_) in perm] # number part
yield npart
for n in range(N,0,-1): # choose from the biggest one
i = npart.index(n) # position of n
j = i+perm[i][1] # i+d
if j>= 0 and j<= N-1 and perm[j][0] < perm[i][0]: # mobile
perm[i], perm[j] = perm[j], perm[i] # swap i and j
break
perm[i][1] *= -1 # change the direction if n is not mobile
return
N = 4
for i, p in enumerate(johntrot(N),1):
if i % N == 1:
print(f"#--------block {i//N+1}---------")
print("#", i, p)
#--------block 1---------
# 1 [1, 2, 3, 4]
# 2 [1, 2, 4, 3]
# 3 [1, 4, 2, 3]
# 4 [4, 1, 2, 3]
#--------block 2---------
# 5 [4, 1, 3, 2]
# 6 [1, 4, 3, 2]
# 7 [1, 3, 4, 2]
# 8 [1, 3, 2, 4]
#--------block 3---------
# 9 [3, 1, 2, 4]
# 10 [3, 1, 4, 2]
# 11 [3, 4, 1, 2]
# 12 [4, 3, 1, 2]
#--------block 4---------
# 13 [4, 3, 2, 1]
# 14 [3, 4, 2, 1]
# 15 [3, 2, 4, 1]
# 16 [3, 2, 1, 4]
#--------block 5---------
# 17 [2, 3, 1, 4]
# 18 [2, 3, 4, 1]
# 19 [2, 4, 3, 1]
# 20 [4, 2, 3, 1]
#--------block 6---------
# 21 [4, 2, 1, 3]
# 22 [2, 4, 1, 3]
# 23 [2, 1, 4, 3]
# 24 [2, 1, 3, 4]
Johnson-Trotterアルゴリズム（再帰的）
この生成された順列をよく見ると４の位置がジグザグに走っていて、さらに各blockを見ると$1,2,3$の順序は同じになっています。
この動きを元にすると再帰的なアルゴリズムが考えられます
Recursive structure (Wikipedia)
(N-1)までの順列が求められたら、その各々に対してNを可能な隙間（外側も含む）に入れていくとNの順列が求まる
これをコードにしました。前と同じ結果が得られます。
# recursive version
def johntrot_rv(n):
if n == 1: return [[1]]
perm = []
for k, pm in enumerate(johntrot_rv(n-1)):
for i in range(n):
i1 = n-1-i if k%2==0 else i
perm += [pm[:i1]+[n]+pm[i1:]]
return perm
for i, p in enumerate(johntrot_rv(4), 1):
print("#", i, p)
指定された順列が何番目に出てくるか
例えば$[2,4,3,1]$が何番目かを以下の順序で考えます。
- 最大値の4を除いた$[2,3,1]$が3つの順列の何番目かを求める（5番目）
- 前に4個のブロックが4つあるので4x4=16
- 現在は5番目で4は右から動くので$[2,4,3,1]$はブロック内で3番目
- したがって$[2,4,3,1]$は$16+3=19$番目
これをコードにすると以下になります。コードは0スタートの順列なので最後に1を足しています。
長さ４のリストなら順番に生成すれば求まりますが、リストが長くなればこ$O(n \log(n))$で解けるこのコードが威力を発揮します。
def f(perm):
if(len(perm)==1):
return 0
i = perm.index(max(perm))
f1 = f(perm[:i]+perm[i+1:])
return f1*len(perm)+(len(perm)-1-i if f1%2==0 else i)
print(f([2, 4, 3, 1])+1)
# 19
【例題】以下の長さ18の順列が何番目めに生成されるか？
[10, 11, 16, 12, 6, 2, 7, 1, 3, 8, 4, 13, 17, 9, 18, 15, 5, 14]
これだけ長くても瞬時に求まります。
P = [10, 11, 16, 12, 6, 2, 7, 1, 3, 8, 4, 13, 17, 9, 18, 15, 5, 14]
print(f(P)+1)
# 6354438534111921
（開発環境：Google Colab）
この考え方はProject Euler、Problem 868: Belfry Mathsを解くのに役に立ちます