順列の生成。

まだ記事にできるほど考えがまとまっているわけではないが，順列の生成の仕方について一つ例を述べておく。

4つの異なる文字 a, b, c, d を並べた順列をすべて生成する際，樹形図などをうまく利用して列挙するのが普通だが，再帰的な手続きを意識した次のような手順を考えた。

基本となる操作として，

（文字列）の先頭の文字と i 番目の文字とを入れ替える

を考え，その結果を (文字列,i) と書くことにする。ただし，i=0 のときは何もしないこととする。

さて，i を 0 から 3 まで動かしながら，この操作を繰り返して最初の文字列 abcd を並べ替えていく。

(abcd,0)=abcd,

((abcd,0),1)=(abcd,1)=bacd,

(((abcd,0),1),2)=(bacd,2)=cabd,

((((abcd,0),1),2),3)=(cabd,3)=dabc.

これは，樹形図でいうと一番目の太い幹（見出し）を生成したことに相当する。

次に，(abcd,0) の後ろの3つの文字について同じ操作を行う。つまり，

a(bcd,0)=abcd,

a((bcd,0),1)=a(bcd,1)=acbd,

a(((bcd,0),1),2)=a(cbd,2)=acdb.

これを他の見出し語に対しても行う。

そしてさらに得られた文字列の各々について，今度は後ろの2文字について同じ操作を行う。つまり，

pq(st,0),

pq((st,0),1)

という操作を行う。

これですべての順列が生成されたことになるはずだが，もとの文字列がただ1文字だけの場合も含めて通用する統一的な形式を望むのであれば，最後の1文字と，その i 番だけ後ろにある文字との入れ替え（結局のところ何もしない空の操作）を実行しておしまい，というオチをつけてもよいだろう。

この再帰的な手続きを疑似的なプログラミング言語で表現したいのだが，実際にどう記述すればよいのかまだ考えが固まっていない。

よくよく考えてみれば，先頭の文字を一つずつ取り去って残りの文字だけで並べ替えを行うという方針は，本質的に樹形図を描くときと違いはない。

それはそれとして，せっかくなので上記の方法でどのように順列が生成されていくのか，その過程を記念に記して本稿のオチとしよう。

なお，最後の1文字に対して無駄な基本操作を行うことを省略した。


【第0段】

abcd

bacd

cabd

dabc

【第1段】

abcd
acbd
adbc

bacd
bcad
bdac

cabd
cbad
cdab

dabc
dbac
dcab

【第2段】

abcd
abdc

acbd
acbd

adbc
adcb


bacd
badc

bcad
bcda

bdac
bdca


cabd
cadb

cbad
cbda

cdab
cdba


dabc
dacb

dbac
dbca

dcab
dcba