C++17 STL Стандартная библиотека шаблонов

 При тестировании кода, который должен работать с последовательностями входных данных, где порядок аргументов не так важен, полезно проверять, получаем ли мы одинаковый результат во всех возможных перестановках для этих входных данных. Такой тест может, например, проверять, корректно ли работает ваш собственный алгоритм сортировки.

Независимо от того, зачем нужны все перестановки для какого-то диапазона значений, std::next_permutation позволит это реализовать. Можно вызвать эту функцию для изменяемого диапазона, и она изменит порядок его элементов на следующую лексикографическую перестановку.

Как это делается

В данном примере мы напишем программу, которая считывает несколько строк, содержащих слова, из стандартного потока ввода, а затем применим функцию std::next_permutation, чтобы сгенерировать и вывести на экран все перестановки для этих строк.

1. Как и обычно, сначала включим все необходимые заголовочные файлы и объявим об использовании пространства имен std:

#include

#include

#include

#include

#include

using namespace std;

2. Мы начнем с вектора строк, который заполним из стандартного потока ввода. Затем отсортируем вектор:

int main()

{

  vector v {istream_iterator{cin}, {}};

  sort(begin(v), end(v));

3. Далее выведем содержимое вектора на консоль. Затем вызовем функцию std::next_permutation. Она систематически перемешивает содержимое вектора, чтобы сгенерировать перестановки этих элементов, которое мы снова выведем на экран. Вызов next_permutation вернет значение false, когда будет сгенерирована последняя перестановка.

  do {

    copy(begin(v), end(v),

         ostream_iterator{cout, ", "});

    cout << '\n';

  } while (next_permutation(begin(v), end(v)));

}

4. Скомпилируем и запустим функцию, передав ей какие-нибудь данные:

$ echo "a b c" | ./input_permutations

a, b, c,

a, c, b,

b, a, c,

b, c, a,

c, a, b,

c, b, a,

Как это работает

Алгоритм std::next_permutation выглядит несколько странным. Это потому, что он принимает только пару итераторов (начальный и конечный) и возвращает значение true, если может найти следующую перестановку. В противном случае он возвращает значение false. Но что вообще означает выражение следующая перестановка?

Алгоритм, с помощью которого функция std::next_permutation находит следующий лексикографический порядок элементов, работает таким образом.

1. Найдем самое большое значение индекса i, для которого выполняется условие v[i-1] < v[i]. Если такого значения нет, то вернем значение false.

2. Теперь найдем самое большое значение индекса j, для которого выполняются условия j >= i и v[j] > v[i-1].

3. Меняем местами элементы на позициях j и i-1.

4. Изменим порядок элементов, находящихся между позицией i и концом диапазона данных, на противоположный.

5. Вернем значение true.

Отдельные порядки перестановки, которые мы получим в результате вызова этой функции, всегда будут появляться в одинаковой последовательности. Чтобы найти все возможные перестановки, мы поначалу отсортировали массив. Это было сделано потому, что если бы ввели строку "c b a", например, то алгоритм завершил бы работу немедленно, так как данная строка представляет собой последний возможный лексикографический порядок элементов.

Инструмент для слияния словарей

 Представьте, что у вас имеется отсортированный список элементов, у кого-то другого появляется другой такой же список и вы хотите обменяться этими списками друг с другом. Самая лучшая идея заключается в том, чтобы объединить оба списка. Их комбинацию нужно отсортировать, поскольку так будет проще найти конкретные элементы.

Данная операция также называется слиянием. Чтобы слить воедино два отсортированных диапазона данных, можно создать новый диапазон и заполнить его элементами из обоих списков. Для каждого перемещения элемента нужно сравнить два элемента наших входных диапазонов данных с целью выбрать самый маленький из оставшихся. В противном случае выходной диапазон не будет отсортирован. Этот процесс показан на рис. 5.6.

Алгоритм std::merge позволяет решить именно эту задачу, поэтому не придется тратить время зря. В данном разделе мы увидим, как пользоваться этим алгоритмом.

Как это делается