## 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`! permutations (where `N`! stands for the
*factorial* of N, the product of all positive integers from 1 to
`N` inclusive).
Algorithms
for enumerating all 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 *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 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:

- It is
*fast:*its time complexity is linear in the length of the array—O(`N`). - It is
*compact:*its space complexity is constant—O(1). It modifies the input array in-place, so that you can call it repeatedly to enumerate all permutations. - It is
*stateless:*no memory overhead is needed for it to keep track of how far along it is in enumerating the permutations. The input array itself is enough to determine the next permutation. - Its output is
*sorted:*it enumerates all permutations in lexicographic order. - Its output has
*no repetitions:*when the input array has duplicate elements, it correctly outputs only distinct permutations.

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).

- 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. - 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`. - Swap
`A`[`i`] and`A`[`j`]. - Reverse the order of the elements from
`A`[`i`+1] to the end of the array, and return True.

To enumerate all 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:

- Set
`ParityFlip`to False. - Find the largest array index
`i`such that`A`[`i`] <`A`[`i`+1]. - If no such
`i`exists:- Reverse the order of
`A`. - If ⌊
`N`/2⌋ is odd, invert the value of`ParityFlip`.

- Reverse the order of
- Otherwise:
- Find the largest array index
`j`such that`A`[`i`] <`A`[`j`]. - Swap
`A`[`i`] and`A`[`j`]. Invert the value of`ParityFlip`. - Reverse the order of the elements from
`A`[`i`+1] to the end of the array. - If ⌊
`M`/2⌋ is odd, where`M`is the number of elements swapped, invert the value of`ParityFlip`.

- Find the largest array index
- 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.