2016年10月16日日曜日

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

という3個の要素を持つリストから2個取り出す組み合わせ()は

の3通りある。

これをに分けて考えてみる。

まず最初の2つのリストは、元のリストから先頭の1を取り除いた残りのリストから1個を取り出す組み合わせ()の結果であるのそれぞれ要素に、取り除いておいた元のリストの先頭要素を加えたものとなっていることがわかる。

次に、は、元のリストから先頭要素を取り除いた残りのリストから2個を取り出す組み合わせ()の結果であるとなっている。

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

を結果のリストに置き換えると

となる。

これを一般化してみる。

はリストの先頭要素

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

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

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

  • またはのときは空リストを返す。
  • のときは一つの空リストを要素とするリストを返す。
  • が空リストのときは一つの空リストを要素とするリストを返す。
  • のときは選び方は一つなので、引数として受け取ったリストをリストにして返す。(例: なら にして返す)
  • r = 1 のときは選び方はn通りあるので、引数として受け取ったリストの各要素をそれぞれリストにして、ネストしたリストを返す。(例: ならにして返す)

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

-- 引数nはリスト 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で5個から3個を取り出す組み合わせを求める

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

組み合わせの公式: で答えが合っているか調べる

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

0 件のコメント:

コメントを投稿