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

  ⇑

Споріднені теми

  ⇑