Generating permutations fast

Question

I run into a performance bottleneck in a program. I have to generate all permutations for a given sequence with size up to n=11.

My code:

#include <algorithm>
#include <chrono>
#include <iostream>
#include <numeric>
#include <vector>
int factorial(int n)
{
 if (n == 0) {
 return 1;
 }
 return n * factorial(n - 1);
}
std::vector<std::vector<int>> generatePermutations(int size)
{
 std::vector<int> sequence(size);
 std::iota(sequence.begin(), sequence.end(), 1);
 std::vector<std::vector<int>> permutations;
 permutations.reserve(factorial(sequence.size()));
 do {
 permutations.emplace_back(sequence);
 } while (std::next_permutation(sequence.begin(), sequence.end()));
 return permutations;
}
int main()
{
 for (int i = 2; i <= 11; ++i) {
 auto t1 = std::chrono::high_resolution_clock::now();
 auto permutations = generatePermutations(i);
 auto t2 = std::chrono::high_resolution_clock::now();
 std::cout << "i:\t" << i << "\tpermutation count:\t" << permutations.size()
 << "\ttime ms:\t"
 << std::chrono::duration_cast<std::chrono::milliseconds>(t2 -
 t1).count() << '\n';
 }
}

The Output:

i: 2 permutation count: 2 time ms: 0
i: 3 permutation count: 6 time ms: 0
i: 4 permutation count: 24 time ms: 0
i: 5 permutation count: 120 time ms: 0
i: 6 permutation count: 720 time ms: 0
i: 7 permutation count: 5040 time ms: 1
i: 8 permutation count: 40320 time ms: 10
i: 9 permutation count: 362880 time ms: 94
i: 10 permutation count: 3628800 time ms: 944
i: 11 permutation count: 39916800 time ms: 10569

As you can see the permutations count gets big very fast because the permutation count is array.size!, e.g. 1*2*3*4*5*6*7*8*9*10*11 for n=11

I need to be a lot faster than 10s for n = 11.

I wonder is there a faster way than using std::next_permutation? Or is there an faster approach with threading?

edit:

Since the requirements were stated as not clear for performance optimizations I want to summarize them here:

-generate all permutations of a given sequence.

-generated permutations don't need to be in a specific order. Currently I use std::next_permuation which generates them in order. Is there an algorithm which does it faster in not specific order?

-generated permutations must be possible to traverse over. In my code I used a std::vector<int> to store each permutation. Any other container is fine too if it is faster.

-generated permutations need to be read but never modified or deleted.

-generation needs to be very fast because the count of permutations gets very high (~40mio permutations for n=11)

• D. Jurcau: What is the challenge actually demanding? Sounds a bit like an XY problem.
• pacmaninbw: For anyone in the Close Vote Queue. The code works and this is a performance question.
• greybeard: If the requirement was to put out permutation count and some measure of time, you'd just need to compute factorials and some values increasing impressively slowly. Guessing there's more to it: Pray present enough context to give helpful reviews - what, in your project, will the result of generatePermutations() be used for? Otherwise, have a look at stdlib's implementation and, say, Python's "on-demand" one, and guess how much room for improvement is left.
• Graipher: So, you don't actually need all the permutations at once, you just need them one at a time? Or do you just need the number of permutations, as you show in your main?
• Sandro4912: I need to store all permutations in a container. Then I inspect them after certain criterias and sort out certain permutations. I think I will ask annother question showing the whole program (If it is not to long with 1400 lines).

Answer 1

The problem here isn't with generating the permutations, it is with memory management. One way to visually see this is to replace the \n at the end of your output with std::endl so you see the results of each iteration at the end of the loop. The delay between the output of the last line and the program ending is all due to freeing memory.

One way to address this is to allocate one big block of memory to hold all the permutations, rather than a bunch of small vectors. Create a class to hold and store all your permutations and handle accessing the results.

Here's a basic implementation of what such a class could look like:

class Permutations {
public:
 Permutations(std::size_t sz);
 /*see below*/operator[](std::size_t elem) const;
 std::size_t size() const { return num_perms; }
private:
 std::size_t num_e; // number of elements we're permuting
 std::size_t num_perms; // total number of permutations
 std::vector<int> permutations;
};
Permutations::Permutations(std::size_t sz): num_e(sz) {
 std::vector<int> sequence(num_e);
 std::iota(sequence.begin(), sequence.end(), 1);
 auto f = factorial(sequence.size());
 num_perms = f;
 permutations.reserve(f * num_e);
 int *p = &permutations[0];
 do {
 std::copy(sequence.begin(), sequence.end(), p);
 p += num_e;
 } while (std::next_permutation(sequence.begin(), sequence.end()));
};

In your main, you'd replace auto permutations = generatePermutations(i); with

Permutations permutations(i);

then access it as you do with the nested vectors. This generates the permutations in much less time.

To access the individual permutations, the operator[] could return a std::vector<int> and copy in the corresponding elements. Other possibilities exist.

To support iterator functionality (like in a range-based for loop), you can create an iterator class and add begin and end members to Permutations.

• Sandro4912: So if I understand correctly the one vector<int> holds all the permutations one after each other? And because we have one continuous space instead of many small ones its faster since only one reallocation happens and not like 40mio with n=11....
• 1201ProgramAlarm: @Sandro4912 That's correct.
• Sandro4912: since I want to read the permutations a lot but never modify them I guess I should return a const std::vector<int>& with operator []
• 1201ProgramAlarm: @Sandro4912 No, because you're constructing the vector to return the permutation, you need to return a complete vector, not a reference (which would be dangling, unless you add a member to the class to hold the constructed vector and avoid the repeated memory allocation costs). Alternatively you could return a pointer to the combination that is stored if you have some other way (or returned value) to know how long it is.
• Sandro4912: I tried your approach but it still takes 6 seconds to generate all permuations for size n=11. Is there a way to reduce the time further?