順列
順列とは「異なるn個の中から 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; }
組み合わせ
次に組み合わせは「異なるn個の中から 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型だと少数切り捨てなので少し不安です。もし確信がある方は教えていただけると嬉しいです。
さいごに
数式さえかければ、かなりシンプルなプログラムで表すことができました。
次は順列・組み合わせの列挙も書けたら書きたいと思います。
ではまた。