c++ - next_permutation() 的并行代码

Question

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

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

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

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

Answer 1

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
     }
   }
   

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

2. 看来您真正想要的是生成从 n 个元素 vector 中提取的 k 个元素集的所有排列。有 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);
   }
   

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