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按字典序生成排列，这意味着生成的排列的前缀也是按字典序排列的。换句话说，您可以通过单独处理每个可能的初始元素来进行非常粗糙的并行化：

//假设v已排序(或对其排序) //此for循环应并行化for (auto n= v.size()，i= 0；i< n；++i) { //复制v，并将'it‘处的元素旋转到开头auto vprime = v；std::rotate( vprime.begin()，vprime.begin() + i，vprime.begin()+i+ 1)；//以上操作可确保vprime1:仍可排序。//因为vprime是常量，所以我们只需要对vprime1进行置换: while (std::next_permutation(vprime.begin() + 1，vprime.end()) { //对vprime做点什么}}

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

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

• 要找到k-组合的所有排列，如果你有一个可以产生所有组合的库函数，那么对每个可能的组合执行next_permutation是一个合理的方法。但请注意，next_combination的许多实现都是为了易于使用而优化的，而不是为了性能。在循环中高效地执行next_combination需要一个持久的状态，这将从根本上降低搜索下一个组合的成本。

另一种方法是使用next_partial_permutation的实现，它直接生成n个元素中k个元素的下一个排列。一个简单的解决方案是基于next_permutation的，但由于需要额外调用std::reverse，这也不是最优的。(值得思考为什么这个算法是有效的。一个提示:如果按字典顺序颠倒序列的第一个排列，则得到按字典顺序排列的最后一个排列。)(代码改编自N2639)

模板bool next_partial_permutation(BidiIt first，BidiIt中间，BidiIt last) {std：：BidiIt(中间，最后)；return std::next_permutation(first，last)；}

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

Answer 2

使用Finding n-th permutation without computing others获得第k个排列，对于k=i*n/count，i从0到count，其中n是排列的数量，i是索引，count是线程的数量。

这将为您提供count块或间隔。在单独线程中的每个间隔内并行迭代，在每个线程中重复调用next_permutation。