演習 16.4 (順列の生成)

Section 19 の説明のとおりプログラムを書こうとすると 分かりにくい人が少なからずいるようなので, もう少し分かりやすい アルゴリズムを紹介する.

1. 与えられたリストを $L$ とし, その長さを $N$ とする.
2. $L$ は $L[0]$ から $L[N-1]$ までの要素をもつ.
3. 結果を保持するリスト $R$ を用意する. 最初は $[]$ にしておく.
4. $I=0$ から $N-1$ に対して次の操作を行う.
   1. $L$ から $L[I]$ を抜いたリストを $LI$ とする.

      (例 $L=[1,2,3,4]$ から $L[1]$ を抜くと $LI=[1,3,4]$)

   2. $LI$ は長さ $N-1$ のリストで, これを引数として自分を呼び出し, $LI$ から生成される順列全てのリスト $RI$ を作る. $RI$ の要素はまたリスト.

      (上の場合, $RI=[[1,3,4],[1,4,3],[3,1,4],[3,4,1], [4,1,3],[4,3,1]]$.)

   3. $RI$ の各要素の先頭に $L[I]$ を付け加える.

      (上の場合, $[[2,1,3,4],[2,1,4,3],[2,3,1,4],[2,3,4,1], [2,4,1,3],[2,4,3,1]]$ となる.)

   4. これを, 結果を保持するリスト $R$ に追加する.

Section 19 ではリストの $I$ 番目に要素を挿入する関数が 必要であった. ここでの方法ではリストの $I$ 番目を抜く関数が必要となる. どちらもほとんど同様なので, 例えば後者を考える. これは, 例えば 重なった $K$ 枚の紙があったとして, その上から $I$ 番目の紙を抜き出す 場合を考えればなにをすればよいか分かると思う. くどいのを承知で説明 すると

1. 一番上から 1 枚ずつとって, 順に隣に重ねる操作を $I$ 回行う
2. 一番上をはずす. (隣には重ねない.)
3. 隣の紙を一枚ずつ順に戻す.

とすればよい.

いずれにしても, 再帰で書くことになるが, 注意すべき点は, 再帰の終点 をどこにするかである. $L$ の長さが 1 の場合に終点とすれば分かりやすい. この場合 $L=[a]$ なら $[[a]]$ を返すようにすればよい. (結果は 順列 (リスト) のリストとなることに注意.) $L=[]$ を終点とすること もできるが, この場合 $[[]]$ (空リストを要素とするリスト) を返す 必要がある. こうしないと, 再帰が進まない.