对于next_permutation并行代码（）(Parallel code for next_pe

我想知道如果我可以并行使用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:

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 } } 
```
上述假定的处理时间每个排列大致相同。如果处理时间与一些初始元素置换是从平均时间与一些其它初始元件排列不同，那么一些线程将他人之前终止，减少了并行化的效果。你可以做并行块通过以上的元素更大的前缀较小。
看来，你真正想要的是制作组从n个元素的矢量绘制的k个元素的所有排列。有N /！（N - K）！ 这样的排列，其迅速变成一个很大的数字。例如，如果n为15，k为10，有10897286400个排列。处理所有的人都会需要一段时间，即使处理也相当快。那么，你是正确的，寻求并行工作的方法。
要找到K-组合的所有排列，执行next_permutation在每个可能的组合是一种合理的方法，如果您有它产生的所有组合的库函数。但要注意，许多实现next_combination是为优化易用性，而不是性能。有效地执行next_combination在一个循环需要一个持久的状态，这将可以从根本上降低搜索的下一个组合的成本。
另一种方法是使用的一种实现next_partial_permutation ，其直接产生k的下一个排列n个元素。一个简单的解决方案是基于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); } 
```
不管如何计算局部排列，则可以使用相同的方法并行化算法如上面所指出的：由前缀组块中的排列（或初始元素，如果处理时间不发生变化），然后执行数据块并行。

Answer 2: