0
\$\begingroup\$

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)

\$\endgroup\$
6
  • 4
    \$\begingroup\$ What is the challenge actually demanding? Sounds a bit like an XY problem. \$\endgroup\$ Commented Feb 19, 2021 at 19:09
  • 4
    \$\begingroup\$ For anyone in the Close Vote Queue. The code works and this is a performance question. \$\endgroup\$ Commented Feb 20, 2021 at 14:17
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ Commented Feb 21, 2021 at 8:49
  • 1
    \$\begingroup\$ 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? \$\endgroup\$ Commented Mar 1, 2021 at 10:45
  • 1
    \$\begingroup\$ 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). \$\endgroup\$ Commented Mar 1, 2021 at 16:46

1 Answer 1

Reset to default
4
\$\begingroup\$

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.

\$\endgroup\$
12
  • 1
    \$\begingroup\$ 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.... \$\endgroup\$ Commented Feb 19, 2021 at 21:10
  • 1
    \$\begingroup\$ @Sandro4912 That's correct. \$\endgroup\$ Commented Feb 19, 2021 at 21:22
  • \$\begingroup\$ 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 [] \$\endgroup\$ Commented Feb 19, 2021 at 22:11
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ Commented Feb 20, 2021 at 0:47
  • \$\begingroup\$ 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? \$\endgroup\$ Commented Feb 20, 2021 at 11:13

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.