c++ - 使用递归和回溯生成所有可能的组合

Question

我正在尝试实现一个类，该类将在给定多个元素和组合大小的情况下生成所有可能的无序 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 循环终止时，程序返回到上一帧，换句话说，回溯。

我一直对递归有疑问，现在我需要将它与回溯相结合以生成所有可能的组合。我做错了什么的任何指示？我应该做什么或者我忽略了什么？

P.S:这是一项大学作业，基本上还包括对有序 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();

    }
  }
}

感谢 Jason 的详尽回复!

Answer 1

考虑形成 N 种组合的一个好方法是将结构看成一棵组合树。然后，遍历该树成为一种自然的方式来思考您希望实现的算法的递归性质，以及递归过程将如何工作。

例如，假设我们有序列 {1, 2, 3, 4}，我们希望找到该集合中的所有 3 种组合。组合的“树”将如下所示:

                              root
                        ________|___
                       |            | 
                     __1_____       2
                    |        |      |
                  __2__      3      3
                 |     |     |      |
                 3     4     4      4

使用先序遍历从根开始遍历，并在到达叶节点时识别组合，我们得到组合:

{1, 2, 3}
{1, 2, 4}
{1, 3, 4}
{2, 3, 4}

所以基本上这个想法是使用索引值对数组进行排序，对于我们递归的每个阶段(在本例中是树的“级别”)，递增到数组中以获得值那将包含在组合集中。另请注意，我们只需要递归 N 次。因此，您将拥有一些递归函数，其签名如下所示:

void recursive_comb(int step_val, int array_index, std::vector<int> tuple);

step_val 指示我们必须递归多远，array_index 值告诉我们在集合中的哪个位置开始向 添加值tuple 和 tuple，一旦我们完成，将成为集合中组合的一个实例。

然后您需要从另一个非递归函数调用 recursive_comb，该函数基本上通过初始化 tuple vector 并输入最大递归步数来“开始”递归过程(即，我们希望元组中的值的数量):

void init_combinations()
{
    std::vector<int> tuple;
    tuple.reserve(tuple_size); //avoids needless allocations
    recursive_comb(tuple_size, 0, tuple);
}

最后，您的 recusive_comb 函数将如下所示:

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

请注意，这不是该算法的最快 版本，因为我们采用了一些我们不需要采用的额外分支，这些分支会产生一些不必要的复制和函数调用等。.. . 但希望它能理解递归和回溯的一般概念，以及两者如何协同工作。