Algorithm for Enumerating Even Permutations


Introduction

Simply put, a permutation of a set of N objects is simply an ordering of the objects into a particular sequence, where each object appears exactly once, without repetition.

If the N objects are distinct, then there are exactly N! possible permutations (where N! stands for the factorial of N, the product of all positive integers from 1 to N inclusive). Algorithms for enumerating all possible permutations abound.

Now, mathematically, permutations can be categorized into odd permutations and even permutations. All permutations can be decomposed into a series of pair-wise swappings. If the N objects are distinct, then the permutations that result from an even number of swaps (even permutations) never coincide with the permutations that result from an odd number of swaps (odd permutations). Whether a permutation is even or odd, is called its parity.

While there are algorithms for determining whether a given permutation is even or odd, there do not appear to be any online resources that discuss how to enumerate all possible even permutations (or, for that matter, how to enumerate all odd permutations).

This page attempts to remedy that.

Enumerating All Permutations

First, we take a look at a particular algorithm among the many that enumerate all possible permutations of a set. Later, we will alter this algorithm so that it enumerates only even permutations. This particular algorithm has some characteristics that make it attractive as our starting point:

The input to this algorithm is an array A of length N, which is initially sorted in non-decreasing order, and its output is a boolean value indicating whether A has been modified to contain the lexicographically next permutation (True), or there are no more permutations and A has been returned to its original non-decreasing order (False).

  1. Find the largest array index i such that A[i] < A[i+1]. If no such index exists, then A is lexicographically the greatest permutation, so transform it back to the lexicographical least permutation by reversing the order of its elements, then return False.
  2. Find the largest array index j such that A[i] <A[j]. Since i+1 is such an index, j can always be found, and is always greater than i.
  3. Swap A[i] and A[j].
  4. Reverse the order of the elements from A[i+1] to the end of the array, and return True.

To enumerate all possible permutations of an array A, we simply sort it in non-decreasing order and run this algorithm repeatedly until it returns False, at which point we have finished enumerating the permutations.

The initial sorting of the array is not necessary, of course, if we store a copy of it somewhere else and simply run the algorithm repeatedly until A returns to its original state.

Enumerating Even Permutations

One way of enumerating all even permutations, of course, is to run an algorithm such as the one we described in the preceding section and apply one of the many parity-finding algorithms on each permutation to determine whether it is even or odd, and discard those that are odd. Unfortunately, algorithms to compute the parity of a permutation tend to be expensive, since the cost of such a computation adds up significantly when we're trying to enumerate all even permutations.

However, if we look closely at the algorithm we described above, we see that actually there's no need to run a separate algorithm for computing the parity of the output permutations: we already have enough information to tell what parity the output will have.

In particular, step (3) always flips the parity of the input array, and the reversal of a segment of the array (step (1) when i cannot be found, and step (4)) changes the parity depending on how many pairs of elements need to be swapped to reverse their order. The latter is a simple computation: to reverse the order of M elements, if M is even, then we simply swap M/2 elements (the front half of the array segment with the back half); if M is odd, the middle element doesn't need to move, so we swap (M-1)/2 elements. In other words, to reverse the order of M elements requires exactly ⌊M/2⌋ swaps. If the number of swaps is odd, the parity of the array is flipped; otherwise, it does not change.

Therefore, to enumerate only even permutations, we simply add a Boolean variable, ParityFlip, to the algorithm to keep track of whether the parity of the input array has been flipped. If the parity is flipped when we are about to return, repeat the algorithm instead of stepping through the next permutation until we reach a permutation that exhibits no parity flip from the input array. This way, if we start with an initial array (which is an even permutation by definition, since zero swaps is an even number of swaps), we will skip over all odd permutations and only return even ones.

In pseudo-code, then, our algorithm to enumerate even permutations is:

  1. Set ParityFlip to False.
  2. Find the largest array index i such that A[i] < A[i+1].
  3. If no such i exists:
    1. Reverse the order of A.
    2. If ⌊N/2⌋ is odd, invert the value of ParityFlip.
  4. Otherwise:
    1. Find the largest array index j such that A[i] <A[j].
    2. Swap A[i] and A[j]. Invert the value of ParityFlip.
    3. Reverse the order of the elements from A[i+1] to the end of the array.
    4. If ⌊M/2⌋ is odd, where M is the number of elements swapped, invert the value of ParityFlip.
  5. If ParityFlip is True, go back to step 2. Otherwise, return.

It may appear on the surface that this algorithm would be quite inefficient due to its outer loop; however, its amortized complexity does not exceed that of the original algorithm. In practice, roughly every 4 consecutively generated permutations will consist of two even and two odd permutations, so even the per-iteration cost is negligible.

Important note: even permutations only make sense when the input array contains only unique elements. If there are duplicate elements, then the set of even permutations is identical to the set of odd permutations, since if a permutation P is obtained through an odd number of swaps, you can make the number of swaps even by simply adding a swap of two identical elements. For this reason, the above algorithm requires that the input array have unique elements; otherwise its output would be incomplete. It is possible to further alter the algorithm to do the “right thing” under all circumstances, but that would sacrifice its efficiency, which is where its value lies.

Download C++ Source Code

The preceding discussion gone way over your head? Not interested in the inner workings but just want some real code you can use? No problem! Just download the C++ implementation of the algorithm for enumerating even permutations.

This implementation uses STL-style templates for maximum reusability. It can enumerate even permutations given any range of an STL bidirectional container, and can be easily extended to user-defined lexicographic orderings. It also has a more careful handling of return values so that it correctly tells you when the array has “rolled over” back to the lexicographically smallest permutation.

Enumerating Odd Permutations

What if you want to enumerate odd permutations instead of even ones? No problem! Relative to an odd permutation, another odd permutation is even (permutations obey the rule that odd + even = odd, and even + even = even). Since our enumeration algorithm works relative to the input array's parity, if you hand it an odd permutation, it will return the next odd permutation. To get an odd permutation in the first place, simply swap the last two elements of the input array. (Swapping any two elements will do, but swapping the last two on a sorted array lets you enumerate all odd permutations in lexicographic order.)

Credits

The algorithm for enumerating all permutations used above is described on Wikipedia's Permutation page. It is credited to 14th century Indian mathematician Narayana Pandita.


Last updated 14 Nov 2010.

Powered by Apache Runs on Debian GNU/Linux Viewable on any browser Valid CSS Valid XHTML 1.1! Proud to be Microsoft-free