[Algo]組合せの数（nＣm）の算出

[はじめに]
・ｎ個の中からｍ個を選ぶ組合せの数（_nＣ_m）を算出するプログラムです。
　例：a、b、cの3個の中から2個を選ぶ組合せは、
　　　ab、ac、bcの3通りであり、その数を数学的表記で『₃Ｃ₂』と表現します。
　.NETのクラスライブラリには算出するメソッドがないようなので作ってみました。
・_nＣ_mを算出する公式はいくつかありますが、
　代表的な公式と各々の特徴について、以下にまとめます。
・参考文献
　『Javaによるはじめてのアルゴリズム入門』

以下に、算出方法に対するプログラム例を示します。
（１）階乗による算出
　公式：_nＣ_m＝n!／｛m!×（n-m）!｝

コードのコピー

/// <summary> /// 異なるn個のものからm個を選ぶ /// 組み合わせの総数 nCmを取得する。 /// </summary> /// <param name="n">n</param> /// <param name="m">m</param> /// <returns>nＣm</returns> public static decimal CalcComb01(decimal n, decimal m) {     //nＣm ＝ nＣm-1 ×（n-m+1）/ m      return CalcFact(n) / (CalcFact(m) * CalcFact(n - m)); } /// <summary> /// 階乗を計算する。 /// </summary> /// <param name="n">n</param> /// <returns>nの階乗（n!）</returns> public static decimal CalcFact(decimal n) {     if (n <= 0m) {         return 1m;     }              return n * CalcFact(n - 1); }

[C#][階乗による算出] 異なるn個のものからm個を選ぶ組み合わせの総数nＣmを取得する。

（２）漸化式による算出
　一般的に、漸化式の計算は再帰処理で実装できます。
　公式：
　(i)m＝0の場合
　　_nＣ_m＝1
　(ii)m＞0の場合
　　_nＣ_m＝_nＣ_m-1×（n-m+1）/m

コードのコピー

/// <summary> /// 異なるn個のものからm個を選ぶ /// 組み合わせの総数 nCmを取得する。 /// </summary> /// <param name="n">n</param> /// <param name="m">m</param> /// <returns>nＣm</returns> public static decimal CalcComb02(decimal n, decimal m) {     //以下の漸化式に従って、再帰により算出する。     //（１）m＝0の場合、     //      nＣm ＝ 1     if (m == 0)     {         return 1;     }     //（２）m≠0の場合、     //      nＣm ＝ nＣm-1 ×（n-m+1）/ m      return CalcComb02(n, m - 1) * (n - m + 1) / m; }

[C#][漸化式による算出] 異なるn個のものからm個を選ぶ組み合わせの総数nＣmを取得する。

（３）Π（パイ）による算出
　「（２）漸化式による算出」の公式は、
　総乗（掛け算を集約したもの）と解釈できるので、
　以下の公式でも表現できます。
　公式：_nＣ_m＝Π{（n-k+1）/k}　（※1≦k≦M）

コードのコピー

/// <summary> /// 異なるn個のものからm個を選ぶ /// 組み合わせの総数 nCmを取得する。 /// </summary> /// <param name="n">n</param> /// <param name="m">m</param> /// <returns>nＣm</returns> public static decimal CalcComb03(decimal n, decimal m) {     //組合せ（nＣm）を、     //以下の公式に従って、ループにより算出する。     //         m     // nＣm ＝ Π {（n-k+1）/ k }     //         k=1     decimal product = 1;     for(decimal k = 1 ; k <= m ; k++)     {         product = product * (n - k + 1) / k;     }     return product; }

[C#][Π（パイ）による算出] 異なるn個のものからm個を選ぶ組み合わせの総数nＣmを取得する。

タグ：アルゴリズム 数学 組合せ コンビネーション