[重複]組み合わせ(nCr,nHr):C++コード

最初に

C++で書かれた、nCrの組み合わせコードです。

表記

組み合わせ
\, _nC_r = \frac{n!}{r!(n-r)!}\,(n\geq r)
重複組み合わせ
\, _nH_r = \, _{n+r-1}C_r

情報

組み合わせ Wikipedia重複組み合わせ Wikipedia

C++コード

/**
* 組み合わせ: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);
}

オンライン実行

コメント 

コメントを残す

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください