はなちるのマイノート

Unityをメインとした技術ブログ。自分らしくまったりやっていきたいと思いますー!

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

はじめに

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

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

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

順列

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

公式はこちら。

 {}_n P_k = \dfrac{n!}{(n-k)!}

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

 \dfrac{n!}{(n-k)!} = n * (n - 1) * ... * (n - k + 1)

/// <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;
}

組み合わせ

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

公式はこちら。

 {}_n C_k = \dfrac{n!}{k!(n-k)!}

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

 \dfrac{n!}{k!(n-k)!} = \dfrac{n*(n-1)*...*(n-k+1)}{k*(k-1)*...*1} = \dfrac{n}{1}*\dfrac{n-1}{2}*...*\dfrac{n-k+1}{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型だと少数切り捨てなので少し不安です。もし確信がある方は教えていただけると嬉しいです。

さいごに

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

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

ではまた。