Return to Question

As you can see the permutations count gets big very fast because it is array.size!.

edit: Other requirements I forgot which maybe help.

The generated permuations can stay const the rest of the program I don't modify them at all after.

Data structure can change. It does not need to be necessary std::vector.

I need to read the generated permutations frequently.

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

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)

I need to read the generated permutations frequently.

#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 << "\ttime ms:\t"
                  << std::chrono::duration_cast<std::chrono::milliseconds>(t2 -
                                                                           t1)
                         .count()
                  << '\n';
    }
}

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

#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';
    }
}

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

edit: Other requirements I forgot which maybe help.

The generated permuations can stay const the rest of the program I don't modify them at all after.

Data structure can change. It does not need to be necessary std::vector.