【C#】順列・組み合わせの数を求める

はじめに

今回は順列・組み合わせの数を求めてみようという記事になります。

ただ列挙するのではなく数を求めることに注意してください。

では早速みていきましょう。

順列

順列とは「異なるｎ個の中から k 個を順番をつけて並べる」ときなどに用いられ、という記号で表されます。

公式はこちら。

これをプログラムしやすいように式変形をすると、このようにかけます。

/// <summary>
/// 順列 (n >= k)
/// </summary>
public static long nPk(long n, long k)
{
    if (n < k) return 0;
    if (n == k) return 1;

    long x = 1;
    for (long i = 0; i < k; i++)
    {
        x = x * (n - i);
    }
    return x;
}

組み合わせ

次に組み合わせは「異なるｎ個の中から k 個を順番をつけずに選ぶ」ときなどに用いられ、という記号で表されます。

公式はこちら。

これをプログラムしやすいように式変形をすると、このようにかけます。

/// <summary>
/// 組み合わせ (n >= k)
/// </summary>
public static long nCk(long n, long k)
{
    if (n < k) return 0;
    if (n == k) return 1;

    long x = 1;
    for (long i = 0; i < k; i++)
    {
        x = x * (n - i) / (i + 1);
    }
    return x;
}

追記)おそらく計算の順番的に大丈夫ですが、long型だと少数切り捨てなので少し不安です。もし確信がある方は教えていただけると嬉しいです。

さいごに

数式さえかければ、かなりシンプルなプログラムで表すことができました。

次は順列・組み合わせの列挙も書けたら書きたいと思います。

ではまた。