# Permutation algorithms. Examples

### Contents

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```