/* * Next lexicographical permutation algorithm (C++) * by Project Nayuki, 2017. Public domain. * https://www.nayuki.io/page/next-lexicographical-permutation-algorithm */ #include #include #include /* * (Template array version) * Computes the next lexicographical permutation of the specified array * of values in place, returning whether a next permutation existed. * (Returns false when the argument is already the last possible permutation.) */ template bool nextPermutation(T array[], std::size_t length) { // Find non-increasing suffix if (length == 0) return false; std::size_t i = length - 1; while (i > 0 && array[i - 1] >= array[i]) i--; if (i == 0) return false; // Find successor to pivot std::size_t j = length - 1; while (array[j] <= array[i - 1]) j--; std::swap(array[i - 1], array[j]); // Reverse suffix std::reverse(&array[i], array + length); return true; } /* * (Template vector version) * Computes the next lexicographical permutation of the specified vector * of values in place, returning whether a next permutation existed. * (Returns false when the argument is already the last possible permutation.) */ template bool nextPermutation(std::vector &vec) { // Find non-increasing suffix if (vec.empty()) return false; typename std::vector::iterator i = vec.end() - 1; while (i > vec.begin() && *(i - 1) >= *i) --i; if (i == vec.begin()) return false; // Find successor to pivot typename std::vector::iterator j = vec.end() - 1; while (*j <= *(i - 1)) --j; std::iter_swap(i - 1, j); // Reverse suffix std::reverse(i, vec.end()); return true; }