最初に

C++で書かれた、重複組み合わせを一つずつ表示するコードです。

表記

重複組み合わせ

情報

重複組み合わせ Wikipedia

C++コード

/**
* n個のものから重複を許して r個とった組み合わせの数で、
* その組み合わせ一つ一つを、派生したクラスのメソッドを、そのつど呼び出す。
*/
class CombinationRepetition
{
public:
    struct Call
    {
        /**
        * 重複組み合わせの一つが決まる毎に呼び出される
        * @param [in] v            組み合わせの数値が入っている
        * @param [in] pUserContext 任意のポインタ
        * @return falseを返すと、強制的に組み合わせの処理が終了する。true の場合、継続する。
        */
        virtual bool VCombinationRepetitionCall(const std::vector<int> &v, void* pUserContext) = 0;
    };
private:
    //!< CombinationRepetition::CallインターフェイスのVCombinationRepetitionCallを呼び出す為のもの
    CombinationRepetition::Call *m_pCaalMethod;
    //!< m_pCaalMethodで登録された、VCombinationRepetitionCallメソッドの引数に渡すポインタ
    void* m_pUserContext;
    //!< 
    std::vector<int> m_vBase;
    //!< n個
    size_t m_n;
    //!< n個のものから重複を許して r個とる数
    size_t m_r;
    //!< n個のものから重複を許して r個とる数
    size_t m_cnt;
private:
    /**
    * 重複組み合わせの入れ子
    * @param [in] baseIdx  m_vBaseのインデックス
    * @param [in] startNum m_vBase[baseIdx] に入る開始番号 
    * @return falseの場合、強制的に組み合わせの処理が終了した。true の場合、通常終了した。
    */
    bool Nest(const size_t baseIdx, const size_t startNum)
    {
        if ( baseIdx == m_r ) {
            ++m_cnt;
            if (m_pCaalMethod) {
                if (!m_pCaalMethod->VCombinationRepetitionCall(m_vBase, m_pUserContext)) {
                    return false;
                }
            }
            return true;
        }

        for (size_t i = startNum; i < m_n; i++) {
            m_vBase[baseIdx] = i;
            if (!Nest(baseIdx + 1, i)) {
                return false;
            }
        }
        return true;
    }
public:
    //! コンストラクタ
    CombinationRepetition() {}
    /**
    * 重複組合せ
    * n個のものから重複を許して r個とった組み合わせの数
    * @param [in] n 要素数
    * @param [in] r n個のものから重複を許して r個とる数
    * @return falseの場合、強制的に組み合わせの処理が終了した。true の場合、通常終了した。
    */
    size_t Run(int n, int r, CombinationRepetition::Call *pCallMethod=nullptr, void* pUserContext=nullptr)
    {
        if (n <= 0 || r <= 0) return false;
        m_cnt = 0;
        m_n = n;
        m_r = r;
        m_pCaalMethod = pCallMethod;
        m_pUserContext = pUserContext;
        m_vBase.resize(r, 0);

        Nest(0, 0);
        return m_cnt;
    }
};

オンライン実行