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