0

Suppose I need to perform some standalone task on every permutation of a sequence. std::next_permutation provides an easy way to iterate over all the permutations in lexicographic order, but suppose I'd like to take advantage of multiple cores by having thread #1 handle permutations 0 to 999,999, thread #2 handle 1,000,000 to 1,999,999, etc.

Is there a way to get the +n th permutation of a sequence aside from calling next_permutation n times?

dlf
  • 9,045
  • 4
  • 32
  • 58
  • It is true that this question has been asked and answered many times. But I believe that you are suffering from the [X Y problem http://meta.stackexchange.com/questions/66377/what-is-the-xy-problem/66378#6637]. What you really want to know is "how can I distribute all the permutations of a sequence between some number of parallel processes?". Converting a number to a permutation index is one possible strategy, but you don't actually need to do that to solve the distribution problem. – rici Aug 02 '14 at 18:35
  • First before you consider running your program in multiple cores or having a parallel program written in OpenMP or pthreads. You should have written a program that performs all computation and permutations as it is suppose to be. This means you already have an algorithm that will compute all of your permutations. And if it works correctly then you can consider writing a parallel program that will take advantage of your computer processors. Without writing a parallel program, you cannot take advantage of your processors. – Juniar Aug 02 '14 at 20:22
  • @rici You're probably right, but in this case the "X" question--how do I divide the job of examining all permutations of a sequence across multiple threads?--is at least borderline off-topic for SO. I understand some of the potential pitfalls of doing things this way, but thought it would be a good place to start as a proof-of-concept. And with help from linked question, it was (worked beautifully). – dlf Aug 02 '14 at 20:25
  • @dfl: Fair enough. In case you care, rough summary: You're looking for the parallel_for_each pattern. If processing takes significantly longer than next_permutation, then that's sufficient. Otherwise, parallel_for_each over the permutation prefixes of some fixed length, and have each task do all the suffix permutations (appended to the specific prefix). – rici Aug 02 '14 at 21:10

0 Answers0