Using recursion and backtracking to generate all possible combinations
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() 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
};
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
}
}
}
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";
}
}
}
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: This is a college assignment that also includes basically doing the same thing for ordered n-tuples.
Thanks in advance!
/////////////////////////////////////////////////////////////////////////////////////////
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();
}
}
And for the case of ordered n-tuples:
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();
}
}
}
Thank you Jason for your thorough response!
Answer
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.
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}
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);
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.
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);
}
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;
}
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.