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

概述我试图实现一个类,它将生成所有可能的无序n元组或组合,给出了许多元素和组合的大小. 换句话说,当调用这个时： NTupleUnordered unordered_tuple_generator(3, 5, print);unordered_tuple_generator.Start(); print()是在构造函数中设置的回调函数. 输出应为： {0,1,2}{0,1,3}{0,1,4}{ 我试图实现一个类,它将生成所有可能的无序n元组或组合,给出了许多元素和组合的大小.

换句话说,当调用这个时：

NTupleUnordered unordered_tuple_generator(3,5,print);unordered_tuple_generator.Start();

print()是在构造函数中设置的回调函数.
输出应为：

{0,1,2}{0,3}{0,4}{0,2,3,4}{1,3}{1,4}{2,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()只是一个kick启动函数来有一个更清晰的接口,它只调用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-loop功能.当循环终止时,
程序返回到前一帧,换句话说,回溯.

我总是有递归的问题,现在我需要将其与回溯结合起来,以生成所有可能的组合.任何指针,我做错了什么？我应该在做什么或我俯瞰？

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(),i) == tuple.end())    {        // add element to the current combination        tuple.push_back(i);        add_element(pos);        tuple.pop_back();    }  }}

谢谢Jason的全面回应！

解决方法 考虑组合N组合的一个好方法是像结构树一样看待结构.遍历该树然后成为考虑您希望实现的算法的递归性质以及递归过程如何工作的自然方式.

比方说,我们有序列{1,4},我们希望找到该集合中的所有3个组合.组合的“树”将如下所示：

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

使用预先遍历遍历根,并在到达叶节点时识别组合,我们得到以下组合：

{1,4}

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

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

其中step_val表示我们必须递归得多远,array_index值告诉我们在集合中我们在哪里开始向元组添加值,一旦完成,元组将是一个组合的实例集合

然后,您需要从另一个非递归函数调用recursive_comb,该非递归函数基本上通过初始化元组向量并输入最大递归步骤(即,元组中我们想要的值的数量)来“递减”循环过程：

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

最后你的recusive_comb函数会像下面这样：

voID recursive_comb(int step_val,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

请注意,这不是算法的最快版本,因为我们正在采取一些额外的分支,我们不需要采取哪些创建一些不必要的复制和函数调用等…但希望它能够跨越一般的想法递归和回溯,以及两者如何协同工作.

总结

以上是内存溢出为你收集整理的c – 使用递归和回溯来生成所有可能的组合全部内容，希望文章能够帮你解决c – 使用递归和回溯来生成所有可能的组合所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。