/* * 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