Skip N permutations in std::next_permutation

Question

I want to know if there is a way to start the iteration over std::next_permutation somewhere other than the beginning. Is this possible?

I tried to change the starting string to the Nth lexographic permutation after a certain number of iterations, but doing that doesn't seem to work correctly, since for the following example it doesn't give 40320 permutations.

#include <algorithm>
#include <string>
#include <iostream>
#include <functional>
#include <vector>
#include <stack>
#include <unordered_set>
#include <chrono>

std::unordered_set<std::string> permutations;

int main()
{
    auto start = std::chrono::high_resolution_clock::now();
    std::string s="ABCDEFGH";
    int partition = 5040;
    int count;

    std::string temp = s;
    
    for (int i=0; i<8; i++)
    {
        count = 0;
        temp = string_permutation((i*partition)+1,temp);
        do 
        {
            permutations.insert(temp);
            
        } while(std::next_permutation(temp.begin(), temp.end()) && (++count != partition));
        
    }
    
    std::cout << permutations.size() << '\n';
    
    auto end = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> diff = end - start;
    
    std::cout << '\n' << diff.count() << " s\n";
}

where the string_permutation function I am using from here

Edward Finkelstein · Accepted Answer · 2022-12-12T17:29:21.887

Apparently this question was asked already: Parallel code for next_permutation()

I tried out the option 1. of the top-rated answer and it definitely works, see below:

#include <iostream>
#include <algorithm>
#include <unordered_set>

using namespace std;

int main()
{
    std::string v = "ABCDEFGH";
    size_t n = v.size();
    unordered_set<std::string> x;
    x.reserve(40320);
    int count = 0;
    for (unsigned int i = 0; i < n; ++i) 
    {
        // Make a copy of v with the element at 'it' rotated to the beginning
        auto vprime = v;
        // cout << vprime << '\n';
        std::rotate(vprime.begin(), vprime.begin() + i, vprime.begin() + i + 1);
        // The above guarantees that vprime[1:] is still sorted.
        // Since vprime[0] is constant, we only need to permute vprime[1:]
        x.insert(vprime);
        count++;
        while (std::next_permutation(vprime.begin() + 1, vprime.end())) 
        {
            x.insert(vprime);
            count++;
        }
        // cout<<count << '\n';
    }
    cout<<count << '\n'; //40320
    cout << x.size() << '\n'; //40320
    return 0;
}

Skip N permutations in std::next_permutation

1 Answers1