测试所有组合（C++）

我认为这是一个经典问题，但我没有找到适合我的问题的答案。我有两个'MyObject'向量，我想遍历第一个向量的元素与第二个元素的所有可能组合，并将所有情况分开处理。（第二个向量可能比第一个向量更多）。这里是我目前在做什么伪代码：测试所有组合（C++）

select_assignement(vector1, vector2, assignement){ 
    vector1_memory = copy(vector1); 
    vector2_memomry = copy(vector2); 

    foreach(element1 in vector1){ 
     foreach(element2 in vector2){ 
      assignement[element1] = element2; 
      vector1_memory.remove(element1); 
      vector2_memory.remove(element2); 
      if(vector1_memory.size()>0) 
       select_assignement(vector1_memory, vector2_memory, assignement); 
      else 
       print_assignment(assignment); // Here I finally get one possible assignement 
     } 
    } 
}

在这里，我认为是向量1小于或等于vector2。所以我给这两个向量之间的每一对'MyObject'赋值，如果剩下一些元素，我会再次递归地执行。我的问题是我必须复制矢量每次递归，因为我无法删除矢量上的一个循环期间的对象...我的问题是：这是做正确的方式，还是我完全疯狂？

感谢您的帮助

编辑：输出为两个列表[a,b,c]和[1,2,3,4]是：

assignement : [a1,b2,c3] 
assignement : [a1,b2,c4] 
... 
assignement : [a4,b3,c2]

来源

2015-05-04 Arcyno

做一个普通的双'for'有什么问题？为什么递归？ – Quentin

double for循环会给我vector1的一个元素与vector2的一个元素之间的所有组合，但不是vector1的整个元素集合与vector2的整个元素集合的所有组合。（或者，也许我设计得这么差） – Arcyno

你的意思是连接'vec1'和'vec2'，然后洗牌得到的'vec3'？或者也许洗牌然后连接？我无法理解你的目标。 – Quentin

其实我觉得使用next_permutation好多了，就像你说的：

void Part::select_assignement(std::vector<MyObject> & vector1, std::vector<MyObject> & vector2){ 
    std::map<MyObject,MyObject> assignement; 
    do { 
     j++; 
     assignement.clear(); 
     for (size_t i = 0; i < vector1.size(); ++i) 
      assignement[vector1[i]] = vector2[i]; 
     treat_this_case(assignement); 
    }while(std::next_permutation(vector2.begin(), vector2.end())); 
}

在我看来，它和以前完全一样，但在一个很简单呃方式。

来源

2015-05-05 08:01:02 Arcyno

这里唯一的是，如果vector2.size（）> vector1.size（），我会得到几个时间相同的组合（当我得到一个排列范围外的排列）...但它不是问题在我的情况。而我的测试表明，它似乎比第一个递归方式快得多。 – Arcyno

测试所有组合（C++）

回答

相关问题