Generating lexicographic permutations with parity

How can we track the parity (odd/even number of transpositions) of all permutations of a sequence?

The following algorithm generates the next permutation that comes lexicographically after a given permutation. Note that it updates the given permutation in-place.

1. Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.
2. Find the largest index l greater than k such that a[k] < a[l].
3. Swap the value of a[k] with that of a[l].
4. Reverse the sequence from a[k + 1] up to and including the final element a[n].

Sometimes, for example when evaluating an \(N\times N\) determinant, we need to know whether reaching the next permutation takes an even or odd number of transpositions.

Speaking of even and odd transpositions, \([a,b,c] \rightarrow [c,a,b]\) requires at least two swaps: first \(b\) and \(c\) are swapped to arrive at \([a,c,b]\), followed by another swap between \(a\) and \(c\). Thus an even number of transpositions is required in total.

The count itself is not fixed, but its parity is. Consider \([a,b,c] \rightarrow [c,b,a]\): we can reach it in one swap (exchange the end elements \(a\) and \(c\)) or in three (add a swap between \(a\) and \(b\) to the previous result), but the number is odd either way. That invariance is why we can speak of the parity of a permutation.

Some visual proofs related to transpositions

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

   

   \(2 N + 1\) is an odd number.

2. The number of transpositions required to reverse a sequence of length \(N\) is \(\lfloor\frac{N}{2}\rfloor\).

   

Representing parity

We represent parity as an integer: \(0\) for even and \(1\) for odd.

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:

5. Relative to the current permutation, the parity flips if and only if \(\lfloor\frac{n-k}{2}\rfloor+1\) is odd.

In the referenced algorithm the last element’s index is \(n\) (see step 4), so the indexing is \(1\)-based. With \(0\)-based indexing, replace \(n\) with \(n-1\) in the formula.

Why the formula works: reaching step 2 guarantees at least one swap of two distinct elements, which contributes odd parity (1) by the first proof. Step 4 reverses a sequence of length \(n - k\), contributing \(\lfloor\frac{n-k}{2}\rfloor\) by the second proof.

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:

template< class BidirIt >
          bool next_permutation( BidirIt first, BidirIt last );

The function permutes the range [first, last) in place. It returns true if the new permutation is lexicographically greater than the previous one, and false once the last permutation is reached, at which point the range resets to the first permutation.

Now we write a new function named next_permutation_parity that has the following signature:

template< class BidirIt >
          bool next_permutation_parity(int& parity,
                                BidirIt first,
                                BidirIt last );

The parity parameter holds the parity indicator (\(0\) for even, \(1\) for odd): on entry, the current parity of [first, last); on return, the parity of the next permutation. Initialize it to \(0\) unless the starting sequence is itself an odd permutation of the lexicographically first.

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

//
// ~~~~~~~~
//
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