らくがき

2008/03/19

[F#] 重複を持たない組合せ(nCm) 



こんな感じかな？　数学音痴なので基本式まんまです(^-^;

コード：

let Combination n m =
  let rec CC n m =
    if m = 0 then
      1
    else 
      let i = CC (n - 1) (m - 1) in
        (n * i / m)
  in
  let i = CC n m in
    i;;

10 C 5 の場合：

Combination 10 5
  CC 10 5
    CC 9 4
      CC 8 3
        CC 7 2
          CC 6 1
            CC 5 0
            = 1 <-- i
          = 6 * 1 / 1 = 6
        = 7 * 6 / 2 = 21
      = 8 * 21 / 3 = 56
    = 9 * 56 / 4 = 126
  = 10 * 126 / 5 = 252
= 252

必ず割り切れるという性質を利用して、毎回割っています。


2008/03/19　-　末尾再帰的に書くとこうだ！

コード：

let Combination (n, m) =
  let rec CC (i, j, res) =
    if j > m then
      res
    else
      CC ((i + 1), (j + 1), (i * res / j))
  in
  CC ((n - m + 1), 1, 1);;

まちがいない！
　
Labels:

posted by BULE! at 19:37

4 Comments:

  • はじめましてこんばんは。hogehoge! いわれてるいげ太です（＾＾

    内包表記的に書くとこうだ！＜マネしてみた

    let combination n m =
    Seq.fold ( * ) 1 { for i in n..(-1)..(n-m+1) -> i }
    / (Seq.fold ( * ) 1 { for i in m..(-1)..1 -> i });;

    By Anonymous Anonymous, at 12:23 AM  

  • はじめまして！
    いげ太さんからコメントもらえるとは驚きです
    ブログをよく読ませて頂いてます(^-^

    内包表記…さっぱりわかりませんが、直感的に書けるみたいで素敵かもかも！

    By Blogger BULE!, at 3:23 PM  

  • > 内包表記…さっぱりわかりませんが
    ごく簡単にいってしまえば、ループしてリストを作ってるだけです。
    （先の例で内包表記が作るのは list ではなく seq ですが）

    同様の機能として、C# にはイテレータ ブロックがありますね。
    ということで、C# コードに変換してみると以下のようになります。

    IEnumerable<int> Numerator(int n, int m)
    {
        for (var i = n; i >= n-m+1; i--)
            yield return i;
    }

    IEnumerable<int> Denominator(int m)
    {
        for (var i = m; i >= 1; i--)
            yield return i;
    }

    int Combination(int n, int m)
    {
        return
            Enumerable.Aggregate<int, int>(Numerator(n, m), 1, (x, y) => x * y)
            / Enumerable.Aggregate<int, int>(Denominator(m), 1, (x, y) => x * y);
    }

    C# では、匿名メソッドで yield が書けないという制約がありますが、
    そこ以外はほぼ同じく書けますね。


    > 直感的に書けるみたいで素敵かもかも！
    実は、先コメントのコードは、もっと簡潔に書けます。
    寝ぼけて for in 書いちゃいましたが、範囲演算子の
    部分だけで OK でした（＾＾；

    let combination n m =
      Seq.fold ( * ) 1 { n..(-1)..(n-m+1) }
      / Seq.fold ( * ) 1 { m..(-1)..1 };;


    長文コメント失礼しました。

    By Anonymous Anonymous, at 10:50 AM  

  • なるほど
    反復処理をサポートするリストを簡単な記述で作れちゃって、
    数学的な表現に近いコーディングを助けるものなんですね。

    これは色々なところで活躍しそうだー

    丁寧な説明をありがとうございます！

    By Blogger BULE!, at 12:25 PM  

Post a Comment

<< Home