Function std.algorithm.sorting.nextEvenPermutation
Permutes range in-place to the next lexicographically greater even
permutation.
bool nextEvenPermutation(alias less, BidirectionalRange)
(
BidirectionalRange range
)
if (isBidirectionalRange!BidirectionalRange && hasSwappableElements!BidirectionalRange);
The predicate less defines the lexicographical ordering to be used on
the range.
An even permutation is one which is produced by swapping an even number of pairs of elements in the original range. The set of even permutations is distinct from the set of all permutations only when there are no duplicate elements in the range. If the range has N unique elements, then there are exactly N!/2 even permutations.
If the range is already the lexicographically greatest even permutation, it is permuted back to the least even permutation and false is returned. Otherwise, true is returned, and the range is modified in-place to be the lexicographically next even permutation.
One can thus generate the even permutations of a range with unique elements by starting with the lexicographically smallest permutation, and repeatedly calling nextEvenPermutation until it returns false.
// Enumerate even permutations
int[] a = [1,2,3,4,5];
do
{
// use the current permutation and
// proceed to the next even permutation of the array.
} while (nextEvenPermutation(a));One can also generate the odd permutations of a range by noting that permutations obey the rule that even + even = even, and odd + even = odd. Thus, by swapping the last two elements of a lexicographically least range, it is turned into the first odd permutation. Then calling nextEvenPermutation on this first odd permutation will generate the next even permutation relative to this odd permutation, which is actually the next odd permutation of the original range. Thus, by repeatedly calling nextEvenPermutation until it returns false, one enumerates the odd permutations of the original range.
// Enumerate odd permutations
int[] a = [1,2,3,4,5];
swap(a[$-2], a[$-1]); // a is now the first odd permutation of [1,2,3,4,5]
do
{
// use the current permutation and
// proceed to the next odd permutation of the original array
// (which is an even permutation of the first odd permutation).
} while (nextEvenPermutation(a));Warning
Since even permutations are only distinct from all permutations
when the range elements are unique, this function assumes that there are no
duplicate elements under the specified ordering. If this is not true, some
permutations may fail to be generated. When the range has non-unique
elements, you should use nextPermutation instead.
Parameters
| Name | Description |
|---|---|
| less | The ordering to be used to determine lexicographical ordering of the permutations. |
| range | The range to permute. |
Returns
false if the range was lexicographically the greatest, in which case the range is reversed back to the lexicographically smallest permutation; otherwise returns true.
Example
// Step through even permutations of a sorted array in lexicographic order
int[] a = [1,2,3];
writeln(nextEvenPermutation(a)); // true
writeln(a); // [2, 3, 1]
writeln(nextEvenPermutation(a)); // true
writeln(a); // [3, 1, 2]
writeln(nextEvenPermutation(a)); // false
writeln(a); // [1, 2, 3]
Example
Even permutations are useful for generating coordinates of certain geometric shapes. Here's a non-trivial example:
import std