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)

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.