最初に
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;
}
};
オンライン実行
関連