Help us understand the problem. What is going on with this article?

Haskellでリストを使って、コンビネーション(C)の計算プログラムを作って遊ぶ

HaskellでコンビネーションCの計算プログラムを作って遊びました。

リストを多用しています。
他にも方法はあるかもしれませんが、リストを使ってみたかっただけです。

combi.hs
c (m,n) = let denom = if m <= 0 || n <= 0 || m < n then [1,1]       --(1)
                      else case m of
                             1 -> [1,1]             --(2)
                             2 -> [2,1]             --(3)
                             x | n == 1 -> [x,1]    --(4)
                               | n == 2 -> [x,x-1]  --(5)
                               | otherwise -> [x,x-1..x-n+1]     --(6)
              nume = if n <= 0 || m < n then [1,1]      --(7)
                     else case n of
                             1 -> [1,1]             --(8)
                             2 -> [2,1]             --(9)
                             x -> [n,n-1..1]        --(10)

          in
              (foldl (*) (head denom) (tail denom)) / (foldl (*) (head nume) (tail nume))     --(11)

main::IO()
main = do
    let conbi = [(10,9),(9,9),(8,3),(7,-2),(1,3)]
    print (map c conbi)

実行結果は

[10.0, 1.0, 56.0, 1.0, 1.0]

となります。(リストの区切りが見にくかったので、スペースを入れました。)

解説

上記のプログラムは、c (m,n)関数とmain関数で構成されています。

関数cの引数は、(m,n)という、2つの値からなるタプルです。
mCnを表しています。
main関数内のconbiは、計算したいコンビネーションをタプルで表したリストになります。
そのリストの各要素を引数にして関数cを呼び出しています。(map関数は、第1引数の関数に、第2引数のリストの各要素を適用して、その結果のリストを返します。)

関数cの内部ではどのような処理をしているでしょうか?

先ずは、denomの定義から。

combi.hs
             let denom = if m <= 0 || n <= 0 || m < n then [1,1]       --(1)
                      else case m of
                             1 -> [1,1]             --(2)
                             2 -> [2,1]             --(3)
                             x | n == 1 -> [x,1]    --(4)
                               | n == 2 -> [x,x-1]  --(5)
                               | otherwise -> [x,x-1..x-n+1]     --(6)

denomは、『分母』のスペルの前半分くらい。
(1)では、mnが負だった場合や、mのほうが小さい場合、そのようなコンビネーションは計算不可のため、とりあえず、リスト[1,1]を返します。
case-of文は、条件によって処理を分けたい場合に使います。
上記のプログラムでは、mの値によって処理を分けています。
(2)で、mが1の場合、リスト[1,1]を返します(要素が1つのリストになると都合が悪いため要素2つのリストを返します(理由は後で説明))。
(3)では、2の時に[2,1]を返します。
(4)以降では、それ以外の値の場合どうするかを記述しています。
それ以外の値の場合を、さらに細かく条件分けしています。
(4)では、nが1の場合、(5)では、nが2の場合です。
(6)は、それ以外の場合です。
コンビネーションの計算するときの分母は、
m×(m-1)×(m-2)×...×(m-n+1)です。
(2)~(6)まで、分母でかける値の一覧をリストにしています。

combi.hs
              nume = if n <= 0 || m < n then [1,1]      --(7)
                     else case n of
                             1 -> [1,1]             --(8)
                             2 -> [2,1]             --(9)
                             x -> [n,n-1..1]        --(10)

次にnumeの定義です。分子です。
(7)は、nが負だった場合や、mのほうが小さい場合、リスト[1,1]を返しています。
(8)(9)(10)は分母の時と同じです。
コンビネーションの計算するときの分子は
n×(n-1)×(n-2)×...×1です。

最後に関数cの戻り値を決定する部分です。

combi.hs
          in
              (foldl (*) (head denom) (tail denom)) / (foldl (*) (head nume) (tail nume))     --(11)

foldl関数は、第2引数を初期値として、第3引数のリストの各要素を順次、第1引数の関数に適用します。
headは、リストの先頭の要素を取り出します。
tailhead以降の要素をリストで返します。
例えば、分母リストdenom[10,9,8,7,6,5]の場合
head denomは、10になります。
tail denomは、[9,8,7,6,5]になります。
つまり、(foldl (*) (head denom) (tail denom))は、
10を初期値として、まずは9(*)に適用するので、10×9
そして次は、その結果と、リストの次の要素をかけます、90×8
それを繰り返します。
よって、10,9,8,7,6,5を全てかけた値が導出されます。

分子を表す部分も同様に考えることができます。

oskats1987
現在C#、F#、Python、Haskell、ディープラーニングを勉強中
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした