[はじめに]
・ｎ個の中からｍ個を選ぶ組合せの数（
nＣ
m）を算出するプログラムです。
例：a、b、cの3個の中から2個を選ぶ組合せは、
ab、ac、bcの3通りであり、その数を数学的表記で『
3Ｃ
2』と表現します。
.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を取得する。 |
