要素数と組み合わせのサイズを指定して、可能なすべての順序付けられていない n-タプルまたは組み合わせを生成するクラスを実装しようとしています。
言い換えれば、これを呼び出すとき：
NTupleUnordered unordered_tuple_generator(3, 5, print);
unordered_tuple_generator.Start();
print() は、コンストラクターで設定されたコールバック関数です。出力は次のようになります。
{0,1,2}
{0,1,3}
{0,1,4}
{0,2,3}
{0,2,4}
{0,3,4}
{1,2,3}
{1,2,4}
{1,3,4}
{2,3,4}
これは私がこれまでに持っているものです:
class NTupleUnordered {
public:
NTupleUnordered( int k, int n, void (*cb)(std::vector<int> const&) );
void Start();
private:
int tuple_size; //how many
int set_size; //out of how many
void (*callback)(std::vector<int> const&); //who to call when next tuple is ready
std::vector<int> tuple; //tuple is constructed here
void add_element(int pos); //recursively calls self
};
これは再帰関数の実装です。Start() は単なるキック スタート関数であり、よりクリーンなインターフェイスを備えています。add_element(0) のみを呼び出します。
void NTupleUnordered::add_element( int pos )
{
// base case
if(pos == tuple_size)
{
callback(tuple); // prints the current combination
tuple.pop_back(); // not really sure about this line
return;
}
for (int i = pos; i < set_size; ++i)
{
// if the item was not found in the current combination
if( std::find(tuple.begin(), tuple.end(), i) == tuple.end())
{
// add element to the current combination
tuple.push_back(i);
add_element(pos+1); // next call will loop from pos+1 to set_size and so on
}
}
}
一定の N サイズの可能なすべての組み合わせを生成したい場合、サイズ 3 の組み合わせを次のように言うことができます。
for (int i1 = 0; i1 < 5; ++i1)
{
for (int i2 = i1+1; i2 < 5; ++i2)
{
for (int i3 = i2+1; i3 < 5; ++i3)
{
std::cout << "{" << i1 << "," << i2 << "," << i3 << "}\n";
}
}
}
N が定数でない場合、それぞれの for ループを独自のフレームで実行することにより、上記の関数を模倣する再帰関数が必要です。for ループが終了すると、プログラムは前のフレームに戻ります。つまり、バックトラックです。
私は常に再帰に問題を抱えていましたが、今ではそれをバックトラッキングと組み合わせて、可能なすべての組み合わせを生成する必要があります。私が間違っていることの指針はありますか？私は何をすべきか、または見落としていますか？
PS: これは、順序付けられた n タプルに対して基本的に同じことを行うことも含む大学の課題です。
前もって感謝します！
/////////////////////////////////////////////// /////////////////////////////////////
他の誰かが同じことを疑問に思っている場合に備えて、正しいコードをフォローアップしたかっただけです。
void NTupleUnordered::add_element( int pos)
{
if(static_cast<int>(tuple.size()) == tuple_size)
{
callback(tuple);
return;
}
for (int i = pos; i < set_size; ++i)
{
// add element to the current combination
tuple.push_back(i);
add_element(i+1);
tuple.pop_back();
}
}
順序付けられた n タプルの場合は、次のようになります。
void NTupleOrdered::add_element( int pos )
{
if(static_cast<int>(tuple.size()) == tuple_size)
{
callback(tuple);
return;
}
for (int i = pos; i < set_size; ++i)
{
// if the item was not found in the current combination
if( std::find(tuple.begin(), tuple.end(), i) == tuple.end())
{
// add element to the current combination
tuple.push_back(i);
add_element(pos);
tuple.pop_back();
}
}
}
丁寧な回答をありがとう、ジェイソン！