Using recursion and backtracking to generate all p

问题:

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!

回答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.

回答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;
    }

回答3:

In MATLAB:

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% combinations.m

function combinations(n, k, func)
assert(n >= k);
n_set = [1:n];
k_set = zeros(k, 1);
recursive_comb(k, 1, n_set, k_set, func)
return

function recursive_comb(k_set_index, n_set_index, n_set, k_set, func)
if k_set_index == 0,
  func(k_set);
  return;
end;
for i = n_set_index:length(n_set)-k_set_index+1,
  k_set(k_set_index) = n_set(i);
  recursive_comb(k_set_index - 1, i + 1, n_set, k_set, func); 
end;
return;

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Test:
>> combinations(5, 3, @(x) printf('%s\n', sprintf('%d ', x)));
3 2 1 
4 2 1 
5 2 1 
4 3 1 
5 3 1 
5 4 1 
4 3 2 
5 3 2 
5 4 2 
5 4 3