C言語でnCr（組み合わせ）とnPr（順列）を求めるプログラム

Cプログラミングにおいて、nCrは組み合わせ（combination）と呼ばれます。nCrとは、n個の要素からなる集合からr個の要素を選び出す方法の数を指し、このとき選ぶ順序は考慮されません。

一方、nPrは順列（permutation）と呼ばれます。nPrとは、n個の要素からなる集合からr個の要素を取り出し、順序や並び方を考慮して配置する方法の数です。

順列・組み合わせの公式

C言語で与えられた数値の順列と組み合わせを求めるための公式は、以下の通りです。

• nCr = n! / (r! × (n-r)!)
• nPr = n! / (n-r)!

nCrを求める際のロジックは次のようになります。

result = factorial(n)/(factorial(r)*factorial(n-r));

nPrを求める際のロジックは次のようになります。

result = factorial(n)/factorial(n-r);

ここで使用されるfactorial()は、引数として受け取った整数の階乗（n!）を計算して返す関数です。階乗とは、1からその数までのすべての正の整数を掛け合わせた値のことです。

サンプルコード

以下は、入力された数値の順列と組み合わせを求めるCプログラムの例です。

#include <stdio.h>
long factorial(int);
long find_ncr(int, int);
long find_npr(int, int);
int main(){
    int n, r;
    long ncr, npr;
    printf("Enter the value of n and r\n");
    scanf("%d%d",&n,&r);
    ncr = find_ncr(n, r);
    npr = find_npr(n, r);
    printf("%dC%d = %ld\n", n, r, ncr);
    printf("%dP%d = %ld\n", n, r, npr);
    return 0;
}
long find_ncr(int n, int r) {
    long result;
    result = factorial(n)/(factorial(r)*factorial(n-r));
    return result;
}
long find_npr(int n, int r) {
    long result;
    result = factorial(n)/factorial(n-r);
    return result;
}
long factorial(int n) {
    int c;
    long result = 1;
    for (c = 1; c <= n; c++)
    result = result*c;
    return result;
}

このプログラムでは、main()関数内でユーザーからnとrの値を入力として受け取り、find_ncr()関数とfind_npr()関数をそれぞれ呼び出して結果を表示します。各関数内部では、factorial()関数を使って階乗を計算し、先述の公式に基づいてnCrおよびnPrを求めています。

実行結果

上記のプログラムをコンパイルして実行すると、次のような出力が得られます。

Enter the value of n and r
5 2
5C2 = 10
5P2 = 20

この例では、5個の中から2個を選ぶ場合、組み合わせ（5C2）は10通り、順列（5P2）は20通りとなります。順列の方が組み合わせより常に大きい（または等しい）のは、順序の違いを別々の並び方として数えるためです。