遍历 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} 并在向量之上调用 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));

遍历 multiset 元素的所有组合

Loop through all combinations of a multiset elements

c++

algorithm

tree

multiset