PRiNTJLEMENTSCcoll ."afterward: "):

/* Генерировать перестановки элементов до тех пор.

* пока элементы не будут упорядочены по убыванию

* - это будет следующая перестановка лосле сортировки

* - по возрастанию, поэтому цикл сразу же завершается */

while (prev permutation(coll-beginO .col 1 .endO)) { PRINT ELEMENTSCcoll . "):

PRiNTJLEMENTSCcoll. "now: "):

/* Генерировать перестановки элементов до тех пор.

* пока элементы не будут упорядочены по убыванию

* - при этой перебираются все возможные перестановки.

* - потому что в исходном состоянии

* - элементы упорядочены по убыванию */

while (prev permutation(coll.beginO.coll.endC))) ( PRiNTJLEMENTSCcoll." "):

PRINT ELEMENTSCcoll."afterward: O;

Результат выполнения программы выглядит так;

on entry: 1 2 3

1 3 2

2 1 3

2 3 1

3 1 2 3 2 1

afterward: 1 2 3 now: 3 2 1

3 1 2

2 3 1

2 1 3

1 3 2

1 2 3

afterward: 3 2 1

Перестановка элементов в случайном порядке

void

random shuffle CRandomAccessIterator beg, RandomAccessIterator end) void

random shuffle (RandomAccessIterator beg, RandomAccessIterator end. RandomFunc& op)

Спасибо Мэтту Остерну (Matt Austern) за это объяснение.

О Первая форма переставляет элементы интервала [beg,end) в случайном порядке, для чего используется генератор случайных чисел с равномерным распределением.

О Вторая форма переставляет элементы интервала [beg,end) с использованием операции ор, вызываемой для целого значения типа difference type итератора: ор{тах). Операция ор возвращает случайное число, большее либо равное О, но меньшее max (возвращать max нельзя).

О Учтите, что операция ор является неконстантной ссылкой, что исключает использование временных значений или обычных функций.

О Сложность линейная (numberOfElements-i обменов).

Возможно, вас интересует, почему алгоритм random shuffle() использует необязательную операцию как неконстантную ссылку. Дело в том, что генераторы случайных чисел обычно обладают локальным состоянием. Старые глобальные функции С (такие, как rand()) хранят свое локальное состояние в статических переменных. Однако такой подход имеет свои недостатки: в частности, генератор случайных чисел в принципе небезопасен по отношению к потокам вьтол-нения (threads), поэтому вы не сможете сгенерировать два независимых потока данных (streams), состоящих из случайных чисел. По этой причине лучше воспользоваться объектами функций, локальное состояние которых инкапсулируется в переменных класса. Но это означает, что генераторы случайных чисел не могут быть константными, потому что они должны изменять свое локальное состояние при создании нового случайного числа. Чтобы генератор случайных чисел не был константным, его можно передать по значению вместо передачи по неконстантной ссылке. Но в этом случае генератор будет копироваться вместе со своим состоянием, и при каждой передаче генератора алгоритму будет генерироваться одна и та же псевдослучайная последовательность. С учетом всех перечисленных факторов было решено передавать генератор по неконстантной ссьшке.

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

Следующий пример демонстрирует случайную перестановку элементов с использованием алгоритма random shuffle():

algo/randoml.cpp finclude <cstdlib> finclude "algostuff-hpp" using namespace std:

class MyRandotn ( public:

ptrdiff t operatorO (ptrdiff t max) { double tmp:

tmp = static cast<double>(rand())

/ static cast<double>CRAND MAX): return static cast<ptrdiff t>(ttiip * max;

int mainO

vector<1nt> coH;

IN5ERT ELEMENT5(coll .1.9): PRINT ELEM£NTS(coll."coll: "):

Случайная перестановка элементов random shuffle (coll.beginO. coll.endO):

PRINTJLEMENTSCcol 1."shuffled: "):

Повторная сортировка

sort (coll.beginO. coll.endO):

PRINT ELEMENTS(col1."sorted: О:

/* Случайная перестановка элементов

* с пользовательским генератором случайных чисел

* - для передачи 1-значения необходимо использовать временный обьект */

MyRandom rd;

random shuffle (coll.beginO, coll.endO. Интервал

rd); Генератор случайных чисел

PRINT ELEMENTS(coll."shuffled: ");

При втором вызове алгоритма random shuffle() используется пользовательский генератор случайных чисел rd(). Он представляет собой объект вспомогательного класса MyRandom, который задействует алгоритм построения случайных чисел, часто обеспечивающий лучший результат по сравнению с прямым вызовом randO

Возможный (но не гарантированный) результат выполнения программы выглядит так:

coll: 123456789 shuffled: 2 6 9 5 4 3 17 8 sorted: 12 3 4 5 6 7 8 9 shuffled: 2 6 9 3 18 7 4 5

Алгоритм построения случайных чисел, используемый в MyRandom, представлен и описан в книге Бьярна Страуструпа «ТЬе С-и- Programming Language*, 3rd Edition.