使用递归和回溯生成所有可能的组合 [英] Using recursion and backtracking to generate all possible combinations
问题描述
我正在尝试实现一个类，该类将在给定许多元素和组合大小的情况下生成所有可能的无序n元组或组合.
I'm trying to implement a class that will generate all possible unordered n-tuples or combinations given a number of elements and the size of the combination.
换句话说，在调用此代码时:
In other words, when calling this:
NTupleUnordered unordered_tuple_generator(3, 5, print);
unordered_tuple_generator.Start();
print()是在构造函数中设置的回调函数. 输出应为:
print() being a callback function set in the constructor. The output should be:
{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}
这是我到目前为止所拥有的:
This is what I have so far:
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);
and this is the implementation of the recursive function, Start() is just a kick start function to have a cleaner interface, it only calls 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大小组合:
If I wanted to generate all possible combinations of a constant N size, lets say combinations of size 3 I could do:
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循环终止时， 程序将返回到上一帧，换句话说就是回溯.
If N is not a constant, you need a recursive function that imitates the above function by executing each for-loop in it's own frame. When for-loop terminates, program returns to the previous frame, in other words, backtracking.
我总是遇到递归问题，现在我需要将其与回溯结合起来以生成所有可能的组合.我在做什么错的任何指示?我应该做什么或被忽略?
I always had problems with recursion, and now I need to combine it with backtracking to generate all possible combinations. Any pointers of what am I doing wrong? What I should be doing or I am overlooking?
P.S:这是一次大学作业，基本上还包括对有序n元组执行相同的操作.
P.S: This is a college assignment that also includes basically doing the same thing for ordered n-tuples.
提前谢谢！
//////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////
只是想跟进正确的代码，以防其他人想知道同一件事.
Just wanted to follow up with the correct code just in case someone else out there is wondering the same thing.
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();
}
}
}
感谢Jason的全面答复！
Thank you Jason for your thorough response!
推荐答案
思考形成N个组合的一种好方法是将结构看成一棵组合树.然后遍历那棵树成为思考您要实现的算法的递归性质以及递归过程如何工作的自然方法.
A good way to think about forming N combinations is to look at the structure like a tree of combinations. Traversing that tree then becomes a natural way to think about the recursive nature of the algorithm you wish to implement, and how the recursive process would work.
例如，假设我们有序列{1, 2, 3, 4}，我们希望找到该集合中的所有3个组合.组合的树"将如下所示:
Let's say for instance that we have the sequence, {1, 2, 3, 4}, and we wish to find all the 3-combinations in that set. The "tree" of combinations would then look like the following:
root
________|___
| |
__1_____ 2
| | |
__2__ 3 3
| | | |
3 4 4 4
使用预遍历从根开始遍历，并在到达叶节点时标识组合，我们得到组合:
Traversing from the root using a pre-order traversal, and identifying a combination when we reach a leaf-node, we get the combinations:
{1, 2, 3}
{1, 2, 4}
{1, 3, 4}
{2, 3, 4}
因此，基本上的想法是使用索引值对数组进行排序，对于递归的每个阶段(在本例中为树的级别")，递增到数组中以获得值将包含在组合集中.还要注意，我们只需要递归N次.因此，您将具有一些递归函数，其签名看起来类似于以下内容:
So basically the idea would be to sequence through an array using an index value, that for each stage of our recursion (which in this case would be the "levels" of the tree), increments into the array to obtain the value that would be included in the combination set. Also note that we only need to recurse N times. Therefore you would have some recursive function whose signature that would look something like the following:
void recursive_comb(int step_val, int array_index, std::vector<int> tuple);
其中step_val指示我们必须递归的距离，array_index值告诉我们我们在集合中的位置，一旦开始，我们便开始向tuple和tuple添加值.重新完成，将是集合中组合的一个实例.
where the step_val indicates how far we have to recurse, the array_index value tells us where we're at in the set to start adding values to the tuple, and the tuple, once we're complete, will be an instance of a combination in the set.
然后，您需要从另一个非递归函数中调用recursive_comb，该函数基本上是通过初始化tuple向量并输入最大递归步数(即我们想要的值个数)来开始"递归过程的元组):
You would then need to call recursive_comb from another non-recursive function that basically "starts off" the recursive process by initializing the tuple vector and inputting the maximum recursive steps (i.e., the number of values we want in the tuple):
void init_combinations()
{
std::vector<int> tuple;
tuple.reserve(tuple_size); //avoids needless allocations
recursive_comb(tuple_size, 0, tuple);
}
最后，您的recusive_comb函数将类似于以下内容:
Finally your recusive_comb function would something like the following:
void recursive_comb(int step_val, int array_index, std::vector<int> tuple)
{
if (step_val == 0)
{
all_combinations.push_back(tuple); //<==We have the final combination
return;
}
for (int i = array_index; i < set.size(); i++)
{
tuple.push_back(set[i]);
recursive_comb(step_val - 1, i + 1, tuple); //<== Recursive step
tuple.pop_back(); //<== The "backtrack" step
}
return;
}
您可以在此处看到此代码的有效示例: http://ideone.com/78jkV
You can see a working example of this code here: http://ideone.com/78jkV
请注意，这不是算法的最快版本，因为我们不需要额外的分支，因此无需创建不必要的复制和函数调用等. ，但希望它能解决递归和回溯的一般概念，以及两者如何协同工作.
Note that this is not the fastest version of the algorithm, in that we are taking some extra branches we don't need to take which create some needless copying and function calls, etc. ... but hopefully it gets across the general idea of recursion and backtracking, and how the two work together.
这篇关于使用递归和回溯生成所有可能的组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
