What is the internal of `next_permutation()` function in c++

Question

Recently I solved a problem of permutation. Then I searched for library function for solve a the problem. I found next_permutation function. Using the function I Solved the problem. I searched a lot to find out the internal of the function but I did not find good sources.

 vector<vector<int>> permute(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>>v;
        do{
            v.push_back(nums);
        }while(next_permutation(nums.begin(), nums.end()));
        return v;
    }

I want to know about the internal of the function. If anyone know about it , please share a code for the function.

Answer 1

Here is the implementation from libstdc++ (same as in SGI STL) simplified and cleaned up a little bit for readability:

template<typename BidirectionalIterator>
bool next_permutation(BidirectionalIterator first, BidirectionalIterator last)
{
    if (first == last)
        return false;
    BidirectionalIterator i = first;
    ++i;
    if (i == last)
        return false;
    i = last;
    --i;

    for(;;)
    {
        BidirectionalIterator ii = i;
        --i;
        if (*i < *ii)
        {
            BidirectionalIterator j = last;
            while (!(*i < *--j)) {}
            std::swap(*i, *j);
            std::reverse(ii, last);
            return true;
        }
        if (i == __first)
        {
            std::reverse(first, last);
            return false;
        }
    }
}

This is a well-known algorithm ("Algorithm L"), see Sec. 7.2.1.2 Generating all permutations in The art of computer programming. Vol. 4A: Combinatorial algorithms, Part 1 by D.E.Knuth.

Idea of the algorithm: for the current permutation, find the longest decreasing subsequence on the right, {...ap ≤ ai > aj > ... > ak}, find the next front element af > ap with the largest possible f in the range [i, k], swap af and ap, and then put the remaining elements in the ascending order, i.e. reverse the subsequence {ai...ap...ak}.