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, 2022 in C++ 131 views

## 1 answer to this question.

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].
• 4,960 points

## 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

## 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

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

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

## 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; ...READ MORE

## Is hiding implementation detail Encapsulation or Abstraction?

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

## Why would anyone use set instead of unordered_set?

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

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

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

## 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