Using recursion and backtracking to generate all possible combinations
Solution 1
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.
Solution 2
Personally I would go with a simple iterative solution.
Represent you set of nodes as a set of bits. If you need 5 nodes then have 5 bits, each bit representing a specific node. If you want 3 of these in your tupple then you just need to set 3 of the bits and track their location.
Basically this is a simple variation on fonding all different subsets of nodes combinations. Where the classic implementation is represent the set of nodes as an integer. Each bit in the integer represents a node. The empty set is then 0. Then you just increment the integer each new value is a new set of nodes (the bit pattern representing the set of nodes). Just in this variation you make sure that there are always 3 nodes on.
Just to help me think I start with the 3 top nodes active { 4, 3, 2 }. Then I count down. But it would be trivial to modify this to count in the other direction.
#include <boost/dynamic_bitset.hpp>
#include <iostream>
class TuppleSet
{
friend std::ostream& operator<<(std::ostream& stream, TuppleSet const& data);
boost::dynamic_bitset<> data; // represents all the different nodes
std::vector<int> bitpos; // tracks the 'n' active nodes in the tupple
public:
TuppleSet(int nodes, int activeNodes)
: data(nodes)
, bitpos(activeNodes)
{
// Set up the active nodes as the top 'activeNodes' node positions.
for(int loop = 0;loop < activeNodes;++loop)
{
bitpos[loop] = nodes-1-loop;
data[bitpos[loop]] = 1;
}
}
bool next()
{
// Move to the next combination
int bottom = shiftBits(bitpos.size()-1, 0);
// If it worked return true (otherwise false)
return bottom >= 0;
}
private:
// index is the bit we are moving. (index into bitpos)
// clearance is the number of bits below it we need to compensate for.
//
// [ 0, 1, 1, 1, 0 ] => { 3, 2, 1 }
// ^
// The bottom bit is move down 1 (index => 2, clearance => 0)
// [ 0, 1, 1, 0, 1] => { 3, 2, 0 }
// ^
// The bottom bit is moved down 1 (index => 2, clearance => 0)
// This falls of the end
// ^
// So we move the next bit down one (index => 1, clearance => 1)
// [ 0, 1, 0, 1, 1]
// ^
// The bottom bit is moved down 1 (index => 2, clearance => 0)
// This falls of the end
// ^
// So we move the next bit down one (index =>1, clearance => 1)
// This does not have enough clearance to move down (as the bottom bit would fall off)
// ^ So we move the next bit down one (index => 0, clearance => 2)
// [ 0, 0, 1, 1, 1]
int shiftBits(int index, int clerance)
{
if (index == -1)
{ return -1;
}
if (bitpos[index] > clerance)
{
--bitpos[index];
}
else
{
int nextBit = shiftBits(index-1, clerance+1);
bitpos[index] = nextBit-1;
}
return bitpos[index];
}
};
std::ostream& operator<<(std::ostream& stream, TuppleSet const& data)
{
stream << "{ ";
std::vector<int>::const_iterator loop = data.bitpos.begin();
if (loop != data.bitpos.end())
{
stream << *loop;
++loop;
for(; loop != data.bitpos.end(); ++loop)
{
stream << ", " << *loop;
}
}
stream << " }";
return stream;
}
Main is trivial:
int main()
{
TuppleSet s(5,3);
do
{
std::cout << s << "\n";
}
while(s.next());
}
Output is:
{ 4, 3, 2 }
{ 4, 3, 1 }
{ 4, 3, 0 }
{ 4, 2, 1 }
{ 4, 2, 0 }
{ 4, 1, 0 }
{ 3, 2, 1 }
{ 3, 2, 0 }
{ 3, 1, 0 }
{ 2, 1, 0 }
A version of shiftBits() using a loop
int shiftBits()
{
int bottom = -1;
for(int loop = 0;loop < bitpos.size();++loop)
{
int index = bitpos.size() - 1 - loop;
if (bitpos[index] > loop)
{
bottom = --bitpos[index];
for(int shuffle = loop-1; shuffle >= 0; --shuffle)
{
int index = bitpos.size() - 1 - shuffle;
bottom = bitpos[index] = bitpos[index-1] - 1;
}
break;
}
}
return bottom;
}
Lechuzza
Updated on February 29, 2020Comments
-
Lechuzza about 4 years
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!
-
Lechuzza about 12 yearsThank you very much! exactly what I was looking for, well explained and thorough. Your code is very similar to mine so I immediately understood what I was doing wrong.
-
Lechuzza about 12 yearsI was looking for a solution using recursion w/backtracking, however your solution is interesting, thanks for the response! +1
-
Jason about 12 years@Loki Astari : +1 for interesting solution. BTW, quick question ... you mentioned this method is iterative, yet it seems like
shiftBitsis called recursively, so in the end this is still a recursive algorithm, right? -
Martin York about 12 years@Jason: Its recursive in the same way addition is recursive. 9999 + 1. => 9+1 = 0 with one over so now I have to add (in tens) 1 + 9 = 0 with one over so now I add (in hundreds) 1 + 9 = 0 with one over so now I add (in thousands) 1 + 9 = 0 with one over so now I have (in 10K) 1. It may use recursion internally to implement a shift operation, butI would not call it a recursive solutionbecause it is not recursing across the result set. Like in the addition example here I am recusing across the 4 digits not across the result set of all 10,000 elements (so I would not call addition recursive).
