/*
* Simple algorithm for enumerating even permutations of a set.
*
* This program is free software: you can redistribute it and/or modify it
* under the terms of the GNU General Public License as published by the Free
* Software Foundation, either version 3 of the License, or (at your option)
* any later version.
*
* This program is distributed in the hope that it will be useful, but WITHOUT
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
* more details.
*
* You should have received a copy of the GNU General Public License along with
* this program. If not, see .
*/
#ifndef _EPERMUTE_H
#define _EPERMUTE_H
#include
/* Templates */
// Permutes the range [first,last) into the lexicographically next even
// permutation of the elements. Starting from a sorted range and calling this
// function repeatedly will enumerate the (N!)/2 even permutations of the
// range.
//
// IMPORTANT: this function assumes that all elements in the range are
// distinct, because only then are even permutations distinct from all
// permutations. The behaviour of this function is undefined if there are
// duplicate elements in the range.
//
// Returns false if there is no lexicographically next permutation, in which
// case the range is transformed into the lexicographically smallest
// permutation; otherwise returns true.
//
// Amortized time complexity is linear; space complexity is O(1).
template
bool next_even_permutation(BidirectionalIterator first,
BidirectionalIterator last);
// Same as the previous function, except that the strict weak ordering comp is
// used to determine lexicographic ordering, instead of operator<().
template
bool next_even_permutation(BidirectionalIterator first,
BidirectionalIterator last, StrictWeakOrdering comp);
/* Template implementations */
template
bool next_even_permutation(BidirectionalIterator first,
BidirectionalIterator last)
{
// Base cases: ranges of 0 or 1 element have no distinct permutations.
// (Neither do 2-element ranges have distinct even permutations; but
// that's taken care of by the main loop.)
if (first == last)
return false;
BidirectionalIterator i = first;
++i;
if (i == last)
return false;
// Enumerate all permutations until we reach an even one.
bool parity = false;
bool ret = true;
do {
// Find last increasing pair of elements in the range.
i = last;
BidirectionalIterator j = --i;
--i;
long n = 1;
while (i != first && *j < *i) {
j = i;
++n;
--i;
}
if (*j < *i) {
// Entire range is decreasing: it's the
// lexicographically greatest. So wrap around.
j = first;
n++;
ret = false;
} else {
// Find last element larger than *i and swap them.
BidirectionalIterator k = last;
while (!(*i < *--k));
std::iter_swap(i, k);
parity = !parity;
}
// Reverse last decreasing range to get lexicographically next
// smallest permutation.
std::reverse(j, last);
if ((n / 2) % 2 == 1)
parity = !parity;
} while (parity);
return ret;
}
template
bool next_even_permutation(BidirectionalIterator first,
BidirectionalIterator last, StrictWeakOrdering comp)
{
// Base cases: ranges of 0 or 1 element have no distinct permutations.
// (Neither do 2-element ranges have distinct even permutations; but
// that's taken care of by the main loop.)
if (first == last)
return false;
BidirectionalIterator i = first;
++i;
if (i == last)
return false;
// Enumerate all permutations until we reach an even one.
bool parity = false;
bool ret = true;
do {
// Find last increasing pair of elements in the range.
i = last;
BidirectionalIterator j = --i;
--i;
long n = 1;
while (i != first && comp(*j, *i)) {
j = i;
++n;
--i;
}
if (comp(*j, *i)) {
// Entire range is decreasing: it's the
// lexicographically greatest. So wrap around.
j = first;
n++;
ret = false;
} else {
// Find last element larger than *i and swap them.
BidirectionalIterator k = last;
while (!comp(*i, *--k));
std::iter_swap(i, k);
parity = !parity;
}
// Reverse last decreasing range to get lexicographically next
// smallest permutation.
std::reverse(j, last);
if ((n / 2) % 2 == 1)
parity = !parity;
} while (parity);
return ret;
}
#endif // _EPERMUTE_H