Dictionary Order
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:
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 (e.g. 1234), 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).
Algorithm
Start from the end and keep comparing.
Find the smallest 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.
j = i + 1
Start from the end and keep comparing.
Find the smallest array element with index k , k < j, from end such that A[k] > A[j]
Swap A[j] and A[k].
Reverse the order of the elements from A[i] to the end of the array, and return True.
Example
Consider a permutation of "1234" p1 = "1342".
Now lets find Next Permutation in lexicographic order.
Start from the end.
Starting with last digit i.e. 2, decrease the counter as long as numbers are in increasing order and find first number that breaks this trend.
In this example we started 2, thus 4 > 2, but 3 < 4, thus the character that break this trend is 3.
Find the smallest element starting from last element 2 such that it is bigger than the element is last step i.e. 3, therefore the element is 4.
Now swap 3 and 4, after this step we get p1' = "1432"
Now reverse the string starting after 4 to the end, which gives us p1'' = "1423".
This gives us smallest number 1423 that is larger than the input number 1342 and thus next in lexicographic order.
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'sno 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 (6) always flips the parity of the input array, and the reversal of a segment of the array (step (2) when i cannot be found, and step (7)) 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 smallest 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.
Otherwise:
j = i + 1
Start from the end and keep comparing.
Find the smallest array element with index k , k < j, from end such that A[k] > A[j]
Swap A[j] and A[k]. Invert the value of ParityFlip.
Reverse the order of the elements from A[i] to the end of the array, and return True.
If ⌊M/2⌋ is odd, where M is the number of elements swapped, invert the value of ParityFlip.
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.
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 worksrelative 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.)
// Narayana's Algorithm // Generates the next permutation in the series in array Digits[] void GeneratePermutation(BYTE *Digits, BYTE numDigits) { // Find the largest index x such that Digits[x] < Digits[x + 1]. short x, y, largestIndex = -1; for(x = (numDigits - 2); x >= 0; x--) { if(Digits[x] < Digits[x+1]) { if(x > largestIndex)largestIndex = x; } } // If no such index exists, the permutation is the last permutation. if(largestIndex == -1)return; // Find the largest index y such that Digits[x] < Digits[y]. // Since x + 1 is such an index, y is well defined and satisfies x < y. x = largestIndex; largestIndex = -1; for(y = (numDigits - 1); y >= 1; y--) { if(Digits[x] < Digits[y]) { if(y > largestIndex)largestIndex = y; } } // Swap Digits[x] with Digits[y]. y = largestIndex; BYTE tmp = Digits[x]; Digits[x] = Digits[y]; Digits[y] = tmp; // Reverse the sequence from Digits[x + 1] up to and including the final element Digits[n]. ++x; y = numDigits - 1; while(y > x) { tmp = Digits[x]; Digits[x] = Digits[y]; Digits[y] = tmp; ++x; --y; } }