C++, Visual C++, Теория

C++. STL. Алгоритмы перестановок

Алгоритмы перестановок. Примеры

Содержание

Поиск на других ресурсах:

1. Алгоритм next_permutation. Сформировать последовательность на основе правила замены текущей перестановки последующей перестановкой

В алгоритме последовательность изменяется путём перестановки соседних элементов. Рассматриваются текущие и последующие элементы, которые затем переставляются на основе заданного условия. Условие может быть задано предикатом.

Алгоритм имеет две перегруженные реализации

template <class BidirectionalIterator>
  bool next_permutation(
  BidirectionalIterator first,
  BidirectionalIterator last);

template <class BidirectionalIterator, class BinaryPredicate>
  bool next_permutation(
  BidirectionalIterator first,
  BidirectionalIterator last,
  BinaryPredicate pred);

где

  • first, last – двунаправленные итераторы, определяющие начало и конец исследуемого диапазона. В пределах этого диапазона происходит перестановка элементов;
  • pred – бинарный (двоичный) предикат, задающий критерий сравнения.

Пример.

#include <iostream>
#include <queue>
#include <vector>
#include <list>
#include <functional>
#include <algorithm>
using namespace std;

// Предикат, определяющий условие алгоритма next_permutation
bool Less_Than(int a, int b)
{
  return a < b;
}

int main()
{
  // Алгоритм next_permutation – сформировать последовательность
  // на основе правила замены текущей перестановки следующей перестановкой.

  // 1. Использование алгоритма без предиката
  // 1.1. Объявить исходный массив
  vector<int> V1 = { 9, 8, 7, 4, 5, 3, 1, 2 };

  // 1.2. Вывести исходный массив
  cout << "V1 => ";
  for (int i : V1)
    cout << i << " ";
  cout << endl;

  // 1.2. Вызвать алгоритм
  next_permutation(V1.begin(), V1.begin() + 3); // сравниваются только первые 3 элемента

  // 1.3. Вывести результирующий массив
  cout << "V1 => ";
  for (int i : V1)
    cout << i << " ";
  cout << endl;

  // 2. Использование алгоритма с предикатом
  // 2.1. Объявить исходный массив
  vector<int> V2 = { 1, 2, 3, 4, 5, 6 };

  // 2.2. Вызвать алгоритм на основе предиката Less_Than
  next_permutation(V2.begin(), V2.end(), Less_Than); // принимаются во внимание все элементы

  // 2.3. Вывести исходный массив
  cout << "V2 => ";
  for (int i : V2)
    cout << i << " ";
  cout << endl;
}

Результат

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. Алгоритм prev_permutation. Сформировать последовательность на основе правила замены текущей перестановки предыдущей

Данный алгоритм отличается от предыдущего тем, что при перестановке элементов рассматриваются текущие и предыдущие элементы. Критерий перестановки может быть задан предикатом.

Алгоритм имеет две перегруженные реализации

template <class BidirectionalIterator>
bool prev_permutation(
  BidirectionalIterator first,
  BidirectionalIterator last);

template <class BidirectionalIterator, class BinaryPredicate>
bool prev_permutation(
  BidirectionalIterator first,
  BidirectionalIterator last,
  BinaryPredicate pred);

где

  • first, last – двунаправленные итераторы, задающие диапазон в котором переставляются элементы;
  • pred – бинарный (двоичный) предикат, задающий критерий сравнения.

Пример.

#include <iostream>
#include <queue>
#include <vector>
#include <list>
#include <functional>
#include <algorithm>
using namespace std;

// Предикат, который определяет условие для алгоритма prev_permutation
bool Less_Than(int a, int b)
{
  return a < b;
}

int main()
{
  // Алгоритм prev_permutation – формирует последовательность таким образом,
  // что текущая перестановка заменяется предыдущей большей (меньшей) перестановкой,
  // если таковая имеется. Критерий сравнения (больше, меньше) задается бинарным предикатом.

  // 1. Использование алгоритма без предиката
  // 1.1. Объявить исходный массив
  vector<int> V1 = { 1, 2, 3, 4, 5, 6, 8, 9 };

  // 1.2. Вызвать алгоритм
  prev_permutation(V1.begin(), V1.begin() + 3); // сравниваются только первые 3 элемента

  // 1.3. Вывести исходный массив
  cout << "V1 => ";
  for (int i : V1)
    cout << i << " ";
  cout << endl;

  // 2. Использование алгоритма с предикатом
  // 2.1. Объявить исходный массив
  vector<int> V2 = { 1, 2, 3, 4, 5, 6 };

  // 2.2. Вызвать алгоритм на основе предиката Less_Than
  prev_permutation(V2.begin(), V2.end(), Less_Than); // принимаются ко вниманию все элементы

  // 2.3. Вывести исходный массив
  cout << "V2 => ";
  for (int i : V2)
    cout << i << " ";
  cout << endl;
}

Результат

V1 => 3 2 1   4 5 6 8 9
V2 => 6 5 4   3 2 1

  ⇑

Связанные темы

  ⇑