順列のアルゴリズム

$[1, 2, 3]$という３個の要素を持つリストから２個取り出す順列（$_3P_2$）は

$_3P_2 = \bigl[\,[1, 2],\;[2, 1]\; [1, 3],\;[3, 1]\; [2, 3]\;[3, 2]\,\bigr]$

の6通りある。

これを先頭要素である$\,1\,$を含んでいる$\;[1, 2], [1, 3]\;[2, 1]\;[3, 1]\;$と、$\,1\,$を含まない$\;[2, 3]\;[3, 2]\;$に分けて考えてみる。

まず$\,1\,$を含む方から$\,1\,$を除いてみると、$[2]$と$[3]$となる。この$\;\Bigl[\,[2],\,[3]\,\Bigr]\;$は、$\;[1,2,3]\;$から先頭要素を取り除いた残りの$\;[2, 3]\;$から一つを取り出すときの順列$(_2P_1)$である。そして、$\;[1 ,2]\;$は$\;1\;$を$\;[2]\;$の先頭に挿入したものであり、また、$\;[2, 1]\;$は$\;[2]\;$の右隣りに挿入したものとなっていることがわかる。$\;[1, 3],\;[3, 1]\;$も同様である。このことから、$\;_3P_2\;$の結果には、先頭要素を取り除いた残りのリストから$\;1\;$個を取り出す順列$(_2P_1)$の結果のそれぞれに、取り除いておいた元のリストの先頭要素$\,1\,$を左から順に位置を変えて挿入したものが含まれているといえる。

次に、$\,1\,$を含まない方を見てみると、$\;\Bigl[\,[2, 3],\, [3,2]\,\Bigr]\;$は、$[2, 3]$から２つを取り出すときの順列$(_2P_2)$となっている。

これを$\;insertion\;$関数（第一引数として挿入する値、第二引数としてリストを取り、値を左から順に異なる位置に挿入したリストのリストを返す。$\;ex:\; insertion\; 1\; [2, 3] \longrightarrow \Bigl[\,[1,2,3], [2,1,3], [2,3,1]\,\Bigr])$と$\,map\,$関数（渡された関数をリストの各要素に適用した結果をリストにまとめる関数）を使って式に表してみると以下のようになる（$\,insertion\,$関数はリストのリストを返すので、それを$\,map\,$した結果はリストのリストを要素として持つリストになる。そのため実際のコードを書くときには、一番外側のリスト減らすためにconcat関数を適用する必要があるが、ここでは見やすさのために省略してある。最後の方にHaskellで書いたコードにはconcat関数を使ってある）。

$_3P_2\; =\;\Bigl(map\; \;(insertion\; 1)\;\; _2P_1\Bigr)\;\; +\;\; _2P_2$

$_2P_1\;$と$\;_2P_2\;$を結果のリストに置き換えると

$_3P_2\; =\;\Bigl( map\; \;(insertion\;1)\;\;\Bigl[\,[2],\,[3]\,\Bigr]\,\Bigr)\;\; +\;\;\Bigl[\,[2,3],\,[3,2]\,\Bigr]$

となる。

これを一般化してみる。

$_nP_r\;=\;\Bigl( map\;\; (insertion\; x)\;\;_{n-1}P_{r-1}\Bigr)\;\;+\;\;_{n-1}P_r$

※$\;x\;$はリストの先頭要素

この式を基にして、n個の要素を持つリストで考えた場合、$\,_nP_r$（n個からr個取り出す順列）を求めるアルゴリズムを文章化すると次のようになる。

1. 先頭要素を除いた$\,n-1\,$個のリストから$\,r-1\,$個を取り出す順列を作る。そして、それぞれの結果に対して最初に取り除いておいた元のリストの先頭要素を挿入する。
2. 次に、先頭要素を除いた$\,n-1\,$個のリストから、今度は$\,r\,$個を取り出す順列を作る。$\,1\,$の場合とは異なり、この結果には取り除いておいた先頭要素は挿入しない。
3. $\,1\,$のリストと$\,2\,$のリストをつなぎあわせたリストが最終的な結果となる

手順$\,1\,$および$\,2\,$はそれぞれ再帰処理となるが、その際の場合分けは次の通り。

• $n\,$が空リストのときは空リストを返す。
• $r = 1\;$のときは選び方は$\,n\,$通りあるので、引数として受け取ったリストの各要素をそれぞれリストにして、ネストしたリストを返す。（例： $\,[a, b, c]\,$なら$\,\Bigl[\,[a], [b], [c]\,\Bigr]\,$にして返す）

これをHaskellで書くとこうなる。

-- 引数ｎはリスト ex:[1,2,3,4,5]
-- 引数rはnから取り出す要素数

nPr :: [a] -> Int -> [[a]]
nPr [] _ = []
nPr n 1 = map (:[]) n
nPr (x:xs) r = (concat $ map (insertion x) $ nPr xs $ r - 1) ++ (nPr xs r)

insertion :: a -> [a] -> [[a]] 
insertion x xs = [insertion' x xs n | n <- [0..(length xs)]]

insertion' :: a -> [a] -> Int -> [a]
insertion' x xs n = take n xs ++ [x] ++ drop n xs

ghciで５個から３個を取り出す順列を求める

ghci> nPr [1..5] 3
[[1,2,3],[2,1,3],[2,3,1],[1,3,2],[3,1,2],[3,2,1],[1,2,4],[2,1,4],[2,4,1],[1,4,2],[4,1,2],[4,2,1],[1,2,5],[2,1,5],[2,5,1],[1,5,2],[5,1,2],[5,2,1],[1,3,4],[3,1,4],[3,4,1],[1,4,3],[4,1,3],[4,3,1],[1,3,5],[3,1,5],[3,5,1],[1,5,3],[5,1,3],[5,3,1],[1,4,5],[4,1,5],[4,5,1],[1,5,4],[5,1,4],[5,4,1],[2,3,4],[3,2,4],[3,4,2],[2,4,3],[4,2,3],[4,3,2],[2,3,5],[3,2,5],[3,5,2],[2,5,3],[5,2,3],[5,3,2],[2,4,5],[4,2,5],[4,5,2],[2,5,4],[5,2,4],[5,4,2],[3,4,5],[4,3,5],[4,5,3],[3,5,4],[5,3,4],[5,4,3]]

length関数で何通りあるか数える

ghci> length $ nPr [1..5] 3
ghci> 60

順列の公式: $\;_nP_r\,=\,\frac {n!}{(n - r)!}\;$で答えが合っているか調べる

ghci> (product [1..5]) `div` (product [1..2]) 
ghci> 60