Алгоритмы next permutation() и prev permutation() пытаются построить следующую или предыдущую перестановку и в случае успеха возвращают true. Если элементы полностью отсортированы по возрастанию, а следующих перестановок не осталось, next permutation() возвращает false. Если же элементы отсортированы по убыванию и не осталось предыдущих перестановок, то previous permutation() возвращает false.

Версии с аргументом StrictWeakOrdering выполняют сравнения, используя бинарный предикат вместо оператора <.

void random shuffle(RandomAccessIterator first.

RandomAccessIterator last): void random shuffle(RandomAccessIterator first.

RandomAccessIterator last. RandomNumberGenerator& rand):

Случайная перестановка элементов в интервале. Алгоритм обеспечивает равномерное распределение результатов только в том случае, если оно обеспечивается генератором случайных чисел. В первой форме задействован внутренний генератор случайных чисел, а второй форме передается пользовательская функция. Генератор должен возвращать значение в интервале [0,п) для некоторого положительного значения п.

Bidirectionallterator partitionCBidirectionalIterator first.

Bidirectionallterator last. Predicate pred): Bidirectional Iterator stable partition(BidirectionalIterator first.

Bidirectionallterator last. Predicate pred):

Элементы, удовлетворяющие предикату pred, перемещаются в начало интервала. Алгоритмы возвращают итератор, установленный в позицию за последним из перемещенных элементов (то есть фактически в позицию конечного итератора для исходного подинтервала элементов, удовлетворяющих предикату pred). Данная позиция часто называется точкой разбиения . Для алгоритма partition() элементы в полученных подинтервалах располагаются в неопределенном порядке, а stable partition() сохраняет элементы до и после точки разбиения в том же относительном порядке, в котором они следовали в исходном интервале.

Следующая программа демонстрирует работу алгоритмов копирования и перестановки элементов.

: C06:Manipulations.cpp Копирование и перестановки {L} Generators NString #include <vector> #include <string> #include <algorithm> #include PrintSequence.h #include NString.h #include Generators.h using namespace std:

int mainO { vector<int> vKlO): Простой подсчет:

generate(vl.begin(), vl.endO. SkipGenO): print(vl.beginO. vl.endO. vl . ):

vector<int> v2(vl.size()):

copy backwarcl(vl.begin(). vl.endO. v2.end());

print(v2.beginO. v2.end(). copy backward . );

reverse copy(vl.begin(). vl.endO, v2.begin());

print(v2.beginO. v2.end(). reverse copy . );

reverseCvl.beginO. vl.endO):

printCvl.beginO. vl.endO. reverse , ):

int half = vl.SizeO / 2:

Интервалы должны иметь одинаковые размеры:

swap ranges(vl.beginO, vl.beginO + half.

vl. beginO + half): print(vl.begin(), vl.endO. swap ranges . ): Сгенерировать интервал заново: generate(vl.begin(). vl.endO. SkipGenO): printCvl.beginO. vl.endO, vl , ): int third = vl.SizeO / 3: forCint i = 0: i < 10: i++) {

rotateCvl.beginO. vl.beginO + third. Vl.endO):

printCvl.beginO. vl.endO. rotate . ):

cout Second rotate example: endl: char c[] = aabbccddeeffgghhiijj : const char CSZ = strlenCc): forCint i = 0: i < 10: i++) {

rotateCc, с + 2, с + CSZ):

printCc, с + CSZ, , ):

cout All n! permutations of abed: endl;

int nf = 4 * 3 * 2 * 1:

char p[] = abed :

forCint i = 0; i < nf: i++) (

next permutationCp. p + 4):

printCp. p + 4, . );

cout Using prev permutation: endl: forCint i = 0: i < nf: i++) {

prev permutation(p, p + 4):

printCp. p + 4, , ):

cout random shuffling a word: endl:

string sC hello ):

cout s endl:

forCint i = 0: i < 5: i++) {

random shuff 1 eСs.beginС). s.endO):

cout s endl:

NString sa[] = { a , b , c . d . a , b .

c . d . a , b . c . d . a , b . c }: const int sasz = sizeof sa / sizeof *sa: vector<NString> nsCsa. sa + sasz): printCns.beginO. ns.endC). ns . ): vector<NString>::iterator it =

partitionCns.beginO, ns.endC). bi nd2ndCgreater<NString>C). b )): cout Partition point: *it endl: printCns.beginC). ns.endC). . ):

Различия между сору() и copybackwarcU) проян.чяются только при частичном порскрьпии мсход-ного и ирпе-миого инторналов. -- Примеч. перса.

Повторная загрузка вектора:

сору (sa, sa + sasz, ns.beginO):

it = stable partition(ns.beginO, ns.endO.

bind2nd(greater<NString>(). b )): cout Stable partition endl: cout Partition point: *it endl; printCns.beginO, ns.endO, , ); } III:-

Чтобы увидеть, как работает эта программа, проще всего запустить ее (вероятно, с перенаправлением вывода в файл).

Сначала мы загружаем вектор vector<int> vl простой возрастающей последовательностью и выводим его. Вы увидите, что алгоритм copy backward() (который копирует данные в вектор v2, по размеру равный vl) приводит к тому же результату, что и обычное копирование алгоритмом сору(), - просто операция выполняется в обратном порядке\

Алгоритм reverse copy() создает копию исходного интервала с элементами, переставленными в обратном порядке, а алгоритм reverse() выполняет перестановку на месте. Далее алгоритм swap ranges() меняет местами верхнюю половину переставленного интервала с нижней.

После воссоздания первоначальной последовательности программа демонстрирует работу алгоритма rotate() на примере многократного сдвига первой трети vl. Во втором примере rotate() используются символы, а сдвиг выполняется на две позиции. Кстати, этот пример также демонстрирует гибкость алгоритмов STL и шаблона print() - они могут работать с массивами char с такой же легкостью, как с любыми другими данными.

Чтобы продемонстрировать работу алгоритмов next permutation() и prev per-mutation(), мы делаем все п! возможных перестановок для набора из четырех символов abcd . Из результатов видно, что перестановки генерируются в строго определенном порядке, то есть процесс их перебора детерминирован.

При простейшей демонстрации алгоритма random shuffle() мы при.меняем его к строке и смотрим, какие слова при этом получаются. У объектов string имеются функции begin() и end(), которые возвращают соответствующие итераторы, что позволяет легко использовать строки со многими алгоритмами STL. Также можно было воспользоваться массивом char.

Напоследок демонстрируются алгоритмы partition() и stable partition() с массивом NString. Обратите внимание: в выражении агрегатной инициализации используются массивы char, но у NString имеется конструктор для char*, который автоматически вызывается в этом случае.

Из выходных данных программы видно, что алгоритм partition() размещает данные до и после точки разбиения правильно, но в непредсказуемом порядке, тогда как алгоритм stable partition() сохраняет их исходный порядок.

Поиск и замена

Алгоритмы группы поиска и замены предназначены для поиска объектов (одного или нескольких) в интервале, определяемом первыми двумя итераторами.