std next permutation Implementation Explanation

0 votes

I was intrigued about how std:next permutation worked, so I pulled the gnu libstdc++ 4.7 version and cleaned the IDs and formatting to create the following sample.

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

template<typename It>
bool next_permutation(It begin, It end)
{
        if (begin == end)
                return false;

        It i = begin;
        ++i;
        if (i == end)
                return false;

        i = end;
        --i;

        while (true)
        {
                It j = i;
                --i;

                if (*i < *j)
                {
                        It k = end;

                        while (!(*i < *--k))
                                /* pass */;

                        iter_swap(i, k);
                        reverse(j, end);
                        return true;
                }

                if (i == begin)
                {
                        reverse(begin, end);
                        return false;
                }
        }
}

int main()
{
        vector<int> v = { 1, 2, 3, 4 };

        do
        {
                for (int i = 0; i < 4; i++)
                {
                        cout << v[i] << " ";
                }
                cout << endl;
        }
        while (::next_permutation(v.begin(), v.end()));
}

My inquiries are as follows: How does it work? 

What do the letters I j, and k mean? 

What importance do they place on the various stages of execution? 

What is an evidence of its accuracy sketch?

Clearly, it just examines the trivial 0 or 1 element list situations before entering the main loop. 

I am pointing to the final element (not one past the end) at the start of the main loop, and the list is at least two elements long.

What is going on in the main loop's body?

Jun 10 in C++ by Nicholas
• 2,460 points
14 views

1 answer to this question.

0 votes
Permutations are generated in lexicographical order by the gcc implementation.

According to Wikipedia, it is as follows:

After a given permutation, the following procedure creates the next permutation lexicographically.

It modifies the current permutation.

1. Determine the highest index k for which a[k] = a[k + 1]. The permutation is the latest permutation if no such index exists.

2. Determine the highest index l for which a[k] = a[l].

l is properly defined and fulfils k l since k + 1 is such an index.

3. Swap a[k] to a[l].

4. Reverse the sequence, starting with a[k + 1] and ending with a[n].
answered Jun 10 by Damon
• 3,580 points

Related Questions In C++

0 votes
0 answers

Intersection of two std::unordered_map

I have two std::unordered_map std::unordered_map<int, int> mp1; std::unordered_map<int, int> ...READ MORE

May 31 in C++ by Nicholas
• 2,460 points
32 views
0 votes
1 answer

How to reverse an std::string?

A reverse function is integrated into C++ and can be used to reverse a string.  This function accepts two parameters: The start iterator for the string The string iterator has come to an end. The following line of code demonstrates how to use this function: #include <iostream> //The library below must be included ...READ MORE

answered Jun 1 in C++ by Damon
• 3,580 points
21 views
0 votes
1 answer

Why is "using namespace std;" considered bad practice?

This has nothing to do with performan ...READ MORE

answered Jun 1 in C++ by Damon
• 3,580 points
34 views
0 votes
1 answer

How to use std::sort to sort an array in C++

We receive std::begin and std::end in C++0x/11, which are overloaded for arrays: #include <algorithm> int main(){ int v[2000]; ...READ MORE

answered Jun 1 in C++ by Damon
• 3,580 points
15 views
0 votes
0 answers

Is hiding implementation detail Encapsulation or Abstraction?

I have seen some people defining abstraction ...READ MORE

May 6 in Java by narikkadan
• 10,840 points
53 views
0 votes
1 answer

Why would anyone use set instead of unordered_set?

Unordered sets must compensate for their O(1) ...READ MORE

answered Jun 1 in C++ by Damon
• 3,580 points
33 views
0 votes
1 answer

What is a smart pointer and when should I use one?

A smart pointer is similar to a ...READ MORE

answered Jun 2 in C++ by Damon
• 3,580 points
10 views
0 votes
1 answer

The new syntax "= default" in C++11

A defaulted default function Object() { [native code] } is defined as a user-defined default function Object() { [native code] } with an empty compound statement and no initialization list. I'll give you an example to demonstrate the difference: #include <iostream> using namespace std; class A { public: ...READ MORE

answered Jun 7 in C++ by Damon
• 3,580 points
11 views
0 votes
1 answer

What data structure is inside std::map in C++?

An associative container is std::map. The standard's ...READ MORE

answered May 31 in C++ by Damon
• 3,580 points
19 views
0 votes
1 answer

How can I convert a std::string to int?

There are some new convert methods in C++ that convert std::string to a numeric type. As an alternative to str.c str() atoi(str.c str()) atoi(str.c str() you can make use of std::stoi std::stoi ...READ MORE

answered Jun 1 in C++ by Damon
• 3,580 points
25 views
webinar REGISTER FOR FREE WEBINAR X
Send OTP
REGISTER NOW
webinar_success Thank you for registering Join Edureka Meetup community for 100+ Free Webinars each month JOIN MEETUP GROUP