組み合わせのアルゴリズム

$[1, 2, 3]$という３個の要素を持つリストから２個取り出す組み合わせ（$_3C_2$）は

$_3C_2 = \Bigl[\,[1, 2],\; [1, 3],\; [2, 3]\,\Bigr]$

の３通りある。

これを$\;[1, 2], [1, 3]\;$と$\;[2, 3]\;$に分けて考えてみる。

まず最初の２つのリスト$[1, 2]$と$[1, 3]$は、元のリスト$[1, 2, 3]$から先頭の1を取り除いた残りのリスト$[2, 3]$から1個を取り出す組み合わせ（$_2C_1$）の結果である$\Bigl[\, [2], [3]\,\Bigr]$のそれぞれ要素に、取り除いておいた元のリストの先頭要素$\,1\,$を加えたものとなっていることがわかる。

次に、$[2, 3]$は、元のリスト$[1, 2, 3]$から先頭要素を取り除いた残りのリスト$[2, 3]$から２個を取り出す組み合わせ（$_2C_2$)の結果である$\Bigl[\, [2, 3]\,\Bigr]$となっている。

これをHaskellの$\;map\;$（引数として渡された関数をリストの各要素に適用して、その結果をリストにまとめる関数）と$\;Cons\,( : )\;$（リストに要素を追加する関数）を使って式に表してみると以下のようになる。

$_3C_2\; =\;\Bigl(map\; \;(1:)\;\; _2C_1\Bigr)\;\; +\;\; _2C_2$

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

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

となる。

これを一般化してみる。

$_nC_r\;=\;\Bigl( map\;\; (x:)\;\;_{n-1}C_{r-1}\Bigr)\;\;+\;\;_{n-1}C_r$

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

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

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

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

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

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

-- 引数ｎはリスト ex:[1,2,3,4,5]
-- 引数rはnから取り出す要素数
nCr n r
    | r < 0 = []
    | length n < r = []　　
    | r == 0 = [[]]
    | length n == r = [n]
    | r == 1 = map (:[]) n
nCr (x:xs) r = (map (x:) (nCr xs $ r - 1) ++ (nCr xs r)

ghciで５個から３個を取り出す組み合わせを求める

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

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

ghci> length $ nCr [1..5] 3
ghci> 10

組み合わせの公式: $\;_nC_r\,=\,\frac {n!}{r!(n - r)!}\;$で答えが合っているか調べる

ghci> product [1..5] `div` (product [1..3] * product [1..(5 - 3)]) 
ghci> 10