c++ - 遍历 multiset 元素的所有组合

Question

我需要找到树中的最佳路径，树是multiset 元素的所有可能组合。例如对于这个 multiset:A - B - C，树将由所有 6 种可能的组合组成:A - B - C |A - C - B |B - A - C |B - C - A |C - A - B |C-B-A

我只想使用多重集遍历这棵树，

像这样:

// I think this must be initialized, but that is not a problem
Path bestPath;

for (mySet::iterator i(aSet.begin()), e(
                    aSet.end()); i != e; ++i) {  
         Path path = someRecursiveFunction(*i);
         if(criteria(bestPath,path))
              bestPath = path;
         return bestPath;
}

和 someRecursiveFunction 可能必须相同，但是循环其余的值，我不想在每个节点中创建一个多重集并将其余的放在上面，因为节点的数量是多重集大小的阶乘，我找不到执行此操作的好方法...

Answer 1

创建一个std::vector如下 std::vector<char> set ={A,B,C}并在 vector 之上调用 std::next_permutation 以获取所有排列

std::next_permutation( std::begin(set), std::end(set));

do {
    //your code for algorithm
    for( auto & x : set)
      std::cout<<x<<" ";
    std::cout<<"\n";
  } while( std::next_permutation( std::begin(set), std::end(set));