Generating lexicographic permutations with parity
Lexicographically ordered permutations
The following algorithm generates the next permutation lexicographically after a given permutation. It changes the given permutation inplace.
 Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.
 Find the largest index l greater than k such that a[k] < a[l].
 Swap the value of a[k] with that of a[l].
 Reverse the sequence from a[k + 1] up to and including the final element a[n].
Sometimes, for example when evaluating an
Speaking of even and odd transpositions,
Some visual proofs related to transpositions

The number of transpositions required to swap two distinct elements in a given sequence is an odd number.

The number of transpositions required to reverse a sequence of length
is$N$ .$\lfloor \frac{N}{2}\rfloor $
Representing parity
The parity of integers is the masure of them being even or odd. The even
integers have the even parity and the odd integers have the odd parity. Thus,
to represent the even parity any even integer can be used. Similarly, to
represent the odd parity any odd integer can be used. To implement this
algorithm we will use the integer
Parity of the next permutation
With the proofs above we can trivially add a step to the algorithm from Wikipedia to find the parity of the next permutation:
 Parity of the new permutation is the same as that of
$$\lfloor \frac{nk}{2}\rfloor +1$$
Note that in the referenced algorithm, the number of elements is
The reasoning behind the formula is as follows: if we reach step 2 of the
algorithm then at least a single swap between two distinct elements is guranteed
that contributes an odd parity (1) as per the first proof above. In the step 4,
we reverse a sequence of length
Implementation in C++
The standard C++ library header <algorithm>
defines the function std::next_permutation
.
Among the many function signatures in the header, we will keep it simple by focusing
on the following declaration:
 Code language
 cpp
template< class BidirIt >
bool next_permutation( BidirIt first, BidirIt last );
Although it may not be obvious from the function signature the description of
the function says that the range [first, last)
will be permuted, or in other
words, the input range will be modified by this function. Also, notice that the
return value is a boolean to indicate whether the generated permutation is
lexicographically greater than the previous permutation. If it returns false,
the last permutation is reached and the range will be reset to the first
permutation.
Now we write a new function named next_permutation_parity
that has the following
signature:
 Code language
 cpp
template< class BidirIt >
bool next_permutation_parity(int& parity,
BidirIt first,
BidirIt last );
The parameter parity
is a reference to an integer to which the parity
indicator (parity
before the function call is the initial parity indicator of the range
[first, last)
. Unless the initial sequence is an odd permutation of the
lexicographically first sequence, the initial value of parity
should be an
even number.
 Code language
 cpp
template< class BidirIt >
bool next_permutation_parity(int& parity,
BidirIt first,
BidirIt last ) {
using std::iter_swap;
using std::reverse;
using std::distance;
BidirIt i = last;
if (first == last  first == i) return false;
for (;;) {
BidirIt ii = i;
i;
if (*i < *ii) {
BidirIt j = last;
while (!(*i < *(j))) {
// do nothing here
}
iter_swap(i, j);
reverse(ii, last);
int p = parity + 1 /* for the single iter_swap */
+ distance(ii, last) / 2;
parity = p % 2;
return true;
}
if (i == first) {
reverse(first, last);
int p = parity + distance(first, last) / 2;
parity = p % 2;
return false;
}
}
}
Demo
 Code language
 cpp
//
// ~~~~~~~~
//
auto str = std::string{"abcd"};
int p = 0;
do {
std::cout << p << " " << str << "\n";
} while (next_permutation_parity(p, str.begin(), str.end()));
//
// ~~~~~~~~
//
Output:
0 abcd
1 abdc
1 acbd
0 acdb
0 adbc
1 adcb
...
0 dcba