next_permutation() 的并行代码

我想知道是否可以使用 OpenMP 并行化此代码。 OpenMP 会让代码运行得更快吗？有更好的方法来实现这一目标吗？

vector<int> t; // already initialized
do{
    // Something with current permutation

} while(next_permutation(t.begin(), t.end()));

我知道我可以轻松并行化for指令，但这里我有一个while (condition = true).

1. next_permutation按字典顺序生成排列，这意味着生成的排列的前缀也按字典顺序排列。换句话说，您可以通过单独处理每个可能的初始元素来进行非常粗略的并行化：

   // Assume that v is sorted (or sort it)
   // This `for` loop should be parallelized
   for (auto n = v.size(), i = 0; i < n; ++i) {
     // Make a copy of v with the element at 'it' rotated to the beginning
     auto vprime = v;
     std::rotate(vprime.begin(), vprime.begin() + i, vprime.begin() + i + 1);
     // The above guarantees that vprime[1:] is still sorted.
     // Since vprime[0] is constant, we only need to permute vprime[1:]
     while (std::next_permutation(vprime.begin() + 1, vprime.end()) {
       // do something with vprime
     }
   }
   

   上面假设每个排列的处理时间大致相同。如果某些初始元素的排列的处理时间与其他某些初始元素的排列的平均时间不同，则某些线程将先于其他线程终止，从而降低并行化的有效性。您可以通过使用大于一个元素的前缀来缩小并行化块。

2. 看来你真正想要的是产生集合的所有排列k从向量中提取的元素n元素。有n!/(n−k）！这样的排列，很快就会变成一个非常大的数字。例如，如果n是 15 并且k是10，有10,897,286,400种排列。即使处理速度相当快，处理所有这些也需要一段时间。所以你寻求并行工作的方法是正确的。

3. 要找到 k 组合的所有排列，执行next_permutation如果您有一个可以生成所有组合的库函数，则对每种可能的组合进行分析是一种合理的方法。但请注意，许多实现next_combination是为了易用性而不是性能而优化的。高效执行next_combination在循环中需要持久状态，这将可以从根本上减少搜索下一个组合的成本。

   另一种方法是使用next_partial_permutation，它直接生成 n 个元素中 k 个的下一个排列。一个简单的解决方案基于next_permutation，但这也是次优的，因为需要额外调用std::reverse。 （值得思考为什么这个算法有效。一个提示：如果你反转序列的字典顺序第一个排列，你就会得到字典顺序最后一个排列。）（代码改编自 N2639）

   template<typename BidiIt>
   bool next_partial_permutation(BidiIt first, BidiIt middle, BidiIt last) {
     std::reverse(middle, last);
     return std::next_permutation(first, last);
   }
   

   无论如何计算部分排列，您都可以使用与上述相同的方法并行化算法：按前缀（或初始元素，如果处理时间不变）对排列进行分块，并并行执行分块。