C++. STL. Permutation algorithms

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

 


Related topics