Function std.algorithm.sorting.nextEvenPermutation

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

Prototype

bool nextEvenPermutation(alias less, BidirectionalRange)(
  BidirectionalRange range
)
if (isBidirectionalRange!BidirectionalRange && hasSwappableElements!BidirectionalRange);

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.

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];
assert(nextEvenPermutation(a) == true);
assert(a == [2,3,1]);
assert(nextEvenPermutation(a) == true);
assert(a == [3,1,2]);
assert(nextEvenPermutation(a) == false);
assert(a == [1,2,3]);

Example

Even permutations are useful for generating coordinates of certain geometric shapes. Here's a non-trivial example:

import std.math : sqrt;

// Print the 60 vertices of a uniform truncated icosahedron (soccer ball)
enum real Phi = (1.0 + sqrt(5.0)) / 2.0;    // Golden ratio
real[][] seeds = [
    [0.0, 1.0, 3.0*Phi],
    [1.0, 2.0+Phi, 2.0*Phi],
    [Phi, 2.0, Phi^^3]
];
size_t n;
foreach (seed; seeds)
{
    // Loop over even permutations of each seed
    do
    {
        // Loop over all sign changes of each permutation
        size_t i;
        do
        {
            // Generate all possible sign changes
            for (i=0; i < seed.length; i++)
            {
                if (seed[i] != 0.0)
                {
                    seed[i] = -seed[i];
                    if (seed[i] < 0.0)
                        break;
                }
            }
            n++;
        } while (i < seed.length);
    } while (nextEvenPermutation(seed));
}
assert(n == 60);