最初に
C++で書かれた、nCrの組み合わせコードです。表記
組み合わせ重複組み合わせ
情報
組み合わせ Wikipedia、重複組み合わせ WikipediaC++コード
/** * 組み合わせ:n個のものから重複無くr個とった組み合わせの数 * @param [in] n 要素数 * @param [in] r n個からr個とる数 * @return 組み合わせ数を返す */ template<typename IntType> IntType nCr(IntType n, IntType r) { if ( r > n ) return 0; if ( r * 2 > n ) r = n - r; if ( r == 0 ) return 1; IntType result = n; for ( IntType i = 2; i <= r; ++i ) { result *= (n - i + 1); result /= i; } return result; }
/** * 重複組合せ * n個のものから重複を許して r個とった組み合わせの数 * @param [in] n 要素数 * @param [in] r n個のものから重複を許して r個とる数 * @return 組み合わせ数を返す */ template<typename IntType> IntType nHr(IntType n, IntType r) { return nCr(n+r-1,r); }