Today, we will delve into the two “permutation wizards” in the C++ standard libraryβ the next_permutation and prev_permutation functions. They are like gymnasts in the world of numbers, elegantly transforming sequences into all possible permutations!
π― Function Usage Instructions
π Function Signatures
// Default comparison using <bool next_permutation(BidirectionalIterator first, BidirectionalIterator last);bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last);// Custom comparison functionbool next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);π οΈ Basic Usage Example
#include <algorithm>#include <vector>#include <iostream>int main() { std::vector<int> vec = {1, 2, 3}; // Generate all ascending permutations do { for (int num : vec) std::cout << num << " "; std::cout << "\n"; } while (std::next_permutation(vec.begin(), vec.end())); return 0;}Output:
1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 βοΈ Underlying Implementation Principles
π Core Algorithm Ideas
These two functions are based on the lexicographical order algorithm, cleverly finding the next or previous permutation:
Steps of the next_permutation algorithm:
1. Find the first ascending pair (i, i+1) from the back, i.e., array[i] < array[i+1]
2. If not found, it means it is the maximum permutation, return false
3. Find the first element array[j] from the back that is greater than array[i]
4. Swap array[i] and array[j]
5. Reverse all elements from i+1 to the end
Steps of the prev_permutation algorithm:
1. Find the first descending pair (i, i+1) from the back, i.e., array[i] > array[i+1]
2. If not found, it means it is the minimum permutation, return false
3. Find the first element array[j] from the back that is less than array[i]
4. Swap array[i] and array[j]
5. Reverse all elements from i+1 to the end
π Time Complexity
Average time complexity: O(n)
Worst-case time complexity: O(n)
Space complexity: O(1)
ποΈ Supported Container Types
β Applicable Containers
These two functions require bidirectional iterators, suitable for:
std::vector
std::deque
std::array
std::string
std::list
Raw arrays
β Not Applicable Containers
Single-direction containers (e.g., std::forward_list)
Associative containers (e.g., std::set, std::map)
Unordered containers (e.g., std::unordered_set)
π Features and Advantages
π Efficient Performance
In-place operation: No extra space needed, directly modifies the original container
Linear time: Each permutation generation only takes O(n) time
Smart skipping: Automatically handles duplicate elements, avoiding duplicate permutations
π¨ Easy to Use
// Easily generate all permutationsstd::string str = "abc";do { std::cout << str << "\n";} while (std::next_permutation(str.begin(), str.end()));π Bidirectional Operation
// Generate permutations both forward and backwardstd::vector<int> vec = {3, 2, 1}; // Generate the previous permutation (ascending direction)do { print(vec);} while (std::prev_permutation(vec.begin(), vec.end()));π― Applicable Scenarios
1. π Generating All Permutations
// Generate all permutations of numbers 1-3std::vector<int> numbers = {1, 2, 3};do { // Process current permutation} while (std::next_permutation(numbers.begin(), numbers.end()));2. π Solving Combination Problems
// Solve the "next greater number" problemstd::vector<int> findNextGreater(std::vector<int> nums) { if (std::next_permutation(nums.begin(), nums.end())) { return nums; } return {}; // No greater permutation}3. π² Generating Random Permutations
// Generate a random starting point, then get subsequent permutationsstd::vector<int> getRandomPermutation(int n) { std::vector<int> result(n); std::iota(result.begin(), result.end(), 1); // Fill 1-n // Randomly shuffle std::random_shuffle(result.begin(), result.end()); // Start generating permutations from a random position std::next_permutation(result.begin(), result.end()); return result;}4. π String Permutations
// Generate all permutations of a stringvoid generateAnagrams(const std::string& str) { std::string temp = str; std::sort(temp.begin(), temp.end()); // Must sort first! do { std::cout << temp << "\n"; } while (std::next_permutation(temp.begin(), temp.end()));}β οΈ Precautions
1. π Must Sort First
The most common mistake: forgetting to sort the sequence first!
// Incorrect examplestd::vector<int> vec = {3, 1, 2}; // Directly calling next_permutation will miss some permutations// Correct approachstd::sort(vec.begin(), vec.end()); // Sort first!do { // Process permutation} while (std::next_permutation(vec.begin(), vec.end()));2. π Handling Duplicate Elements
The function automatically handles duplicate elements and will not generate duplicate permutations:
std::vector<int> vec = {1, 1, 2};std::sort(vec.begin(), vec.end());do { // Only generates 3 permutations instead of 6} while (std::next_permutation(vec.begin(), vec.end()));3. β° Performance Considerations
For large data sizes (n > 10), generating all permutations can be slow:
// For n=12, there are 479 million permutations, use with caution!if (data.size() > 10) { // Consider other algorithms instead of generating all permutations}4. π Iterator Validity
Iterators remain valid during operations, but the order of elements changes:
std::vector<int> vec = {1, 2, 3};auto it = vec.begin() + 1; // Pointing to 2std::next_permutation(vec.begin(), vec.end()); // it remains valid, but the element it points to may change5. π― Custom Comparison Functions
When the element type does not define the < operator, a custom comparison function is needed:
struct Point { int x, y;};bool comparePoints(const Point& a, const Point& b) { return a.x < b.x || (a.x == b.x && a.y < b.y);}std::vector<Point> points = {{1, 2}, {3, 4}, {1, 1}};std::sort(points.begin(), points.end(), comparePoints);do { // Process permutation} while (std::next_permutation(points.begin(), points.end(), comparePoints));π Practical Tips
π‘ Quickly Check for Next Permutation
bool hasNextPermutation(std::vector<int>& nums) { return std::next_permutation(nums.begin(), nums.end());}π Get the k-th Permutation
std::vector<int> getKthPermutation(std::vector<int> nums, int k) { std::sort(nums.begin(), nums.end()); for (int i = 1; i < k; ++i) { std::next_permutation(nums.begin(), nums.end()); } return nums;}π‘οΈ Safe Usage Patterns
template<typename Container>void generateAllPermutations(Container& container) { // Sort first to ensure completeness std::sort(container.begin(), container.end()); // Record the initial state for recovery Container original = container; try { do { processPermutation(container); } while (std::next_permutation(container.begin(), container.end())); } catch (...) { // Restore original state on exception container = std::move(original); throw; } // Restore original state after completion container = std::move(original);}π Performance Comparison
| Method | Time Complexity | Space Complexity | Applicable Scenarios |
|---|---|---|---|
<span><span>next_permutation</span></span> |
O(n) per permutation | O(1) | Requires all permutations |
| Recursive Generation | O(n!) | O(n) | Educational purposes |
| Heap’s Algorithm | O(n!) | O(1) | No duplicate elements |
π Summary
next_permutation and prev_permutation are two gems in the C++ standard library, providing efficient and elegant permutation generation solutions. Remember these key points:
** always sort first** – Must sort before use
** check return value** – Check return value to determine if there are more permutations
** handle duplicates** – The function automatically handles duplicate elements
** consider performance** – Use with caution for large n
Whether for algorithm competitions or practical development, mastering these two “permutation wizards” will make your code cleaner and more efficient! Next time you need to generate permutations, donβt write recursion yourself; let the standard library help you!
Follow us for more in-depth algorithm analyses and programming tips! #AlgorithmDesign #Permutations #C++ #next_permutation #prev_permutation #ProgrammingEducation
π Recommended Learning Resources
Scan to join the γima Knowledge Baseγ computer science knowledge repository for more computer science knowledge.
