nextEvenPermutation

fnbool nextEvenPermutation(alias less = "a < b", BidirectionalRange)(BidirectionalRange range) if (isBidirectionalRange!BidirectionalRange && hasSwappableElements!BidirectionalRange)
  • Permutes range in-place to the next lexicographically greater even
  • permutation.
  • 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