Permutation algorithms. Examples
Contents
- 1. Algorithm next_permutation. Generate a sequence based on the rule of replacing the current permutation with the next permutation
- 2. Algorithm prev_permutation. Generate a sequence based on the rule for replacing the current permutation with the previous one
- Related topics
Search other resources:
1. Algorithm next_permutation. Generate a sequence based on the rule of replacing the current permutation with the next permutation
In the algorithm, the sequence is changed by rearranging neighboring elements. The current and subsequent elements are considered, which are then rearranged based on a given condition. The condition can be specified by a predicate.
The algorithm has two overloaded implementations
template <class BidirectionalIterator> bool next_permutation( BidirectionalIterator first, BidirectionalIterator last); template <class BidirectionalIterator, class BinaryPredicate> bool next_permutation( BidirectionalIterator first, BidirectionalIterator last, BinaryPredicate pred);
where
- first, last – bidirectional iterators that define the beginning and end of the range being examined. Within this range, the elements are rearranged;
- pred – binary (binary) predicate that specifies the comparison criterion.
Example.
#include <iostream> #include <queue> #include <vector> #include <list> #include <functional> #include <algorithm> using namespace std; // A predicate that defines the condition of the next_permutation algorithm bool Less_Than(int a, int b) { return a < b; } int main() { // The next_permutation algorithm - form a sequence based on the rule // for replacing the current permutation with the next permutation. // 1. Using the algorithm without a predicate // 1.1. Declare the original array vector<int> V1 = { 9, 8, 7, 4, 5, 3, 1, 2 }; // 1.2. Output the original array cout << "V1 => "; for (int i : V1) cout << i << " "; cout << endl; // 1.2. Call the algorithm next_permutation(V1.begin(), V1.begin() + 3); // only the first 3 elements are compared // 1.3. Output the resulting array cout << "V1 => "; for (int i : V1) cout << i << " "; cout << endl; // 2. Using algorithm with a predicate. // 2.1. Declare the source array vector<int> V2 = { 1, 2, 3, 4, 5, 6 }; // 2.2. Call the algorithm based on the Less_Than predicate next_permutation(V2.begin(), V2.end(), Less_Than); // all elements are considered // 2.3. Output the original array cout << "V2 => "; for (int i : V2) cout << i << " "; cout << endl; }
Result
V1 => 9 8 7 4 5 3 1 2 V1 => 7 8 9 4 5 3 1 2 V2 => 1 2 3 4 6 5
⇑
2. Algorithm prev_permutation. Generate a sequence based on the rule for replacing the current permutation with the previous one
This algorithm differs from the previous one in that the current and previous elements are considered when permuting elements. The permutation criterion can be given by a predicate.
The algorithm has two overloaded implementations
template <class BidirectionalIterator> bool prev_permutation( BidirectionalIterator first, BidirectionalIterator last); template <class BidirectionalIterator, class BinaryPredicate> bool prev_permutation( BidirectionalIterator first, BidirectionalIterator last, BinaryPredicate pred);
where
- first, last – bidirectional iterators that specify the range in which the elements are rearranged;
- pred – binary (binary) predicate that specifies the comparison criterion.
Example.
#include <iostream> #include <queue> #include <vector> #include <list> #include <functional> #include <algorithm> using namespace std; // A predicate that defines a condition for the prev_permutation algorithm bool Less_Than(int a, int b) { return a < b; } int main() { // prev_permutation algorithm - generates a sequence in such a way // that the current permutation is replaced by the previous larger (smaller) // permutation, if any. The comparison criterion (greater than, less than) // is given by a binary predicate. // 1. Using the algorithm without a predicate // 1.1. Declare the original array vector<int> V1 = { 1, 2, 3, 4, 5, 6, 8, 9 }; // 1.2. Call algorithm prev_permutation(V1.begin(), V1.begin() + 3); // only the first 3 elements are compared // 1.3. Output the original array cout << "V1 => "; for (int i : V1) cout << i << " "; cout << endl; // 2. Using the algorithm with a predicate // 2.1. Declare the source array vector<int> V2 = { 1, 2, 3, 4, 5, 6 }; // 2.2. Call algorithm based on Less_Than predicate prev_permutation(V2.begin(), V2.end(), Less_Than); // all elements are considered. // 2.3. Output the source array cout << "V2 => "; for (int i : V2) cout << i << " "; cout << endl; }
Result
V1 => 3 2 1 4 5 6 8 9 V2 => 6 5 4 3 2 1
⇑
Related topics
- Algorithms for working with data which are presented according to the heap principle. Algorithms make_heap, push_heap, pop_heap, sort_heap
- Algorithms for determining the minimum and maximum. Algorithms min, min_element, max, max_element, lexicographical_compare
- Non-modifying algorithms. Search. Examples. Algorithms find, find_if, find_first_of, find_end, adjanced_find, search, search_n
- Non-modifying algorithms. Algorithms count, count_if, equal, equal_range, mismatch
- Algorithms for working with sets. Algorithms includes, set_union, set_intersection, set_difference, set_symmetric_difference
- Modifying algorithms. Part 1. Algorithms that change all elements of a sequence. Algorithms for_each, transform, fill, fill_n, generate, generate_n
- Modifying algorithms. Part 2. Algorithms for exchanging values of sequence elements. Algorithms swap, swap_ranges, iter_swap
⇑