Перестановка элементов

bool

next permutation (Bidirectionallterator beg. Bidirectionallterator end) bool

prev permutation (Bidirectionallterator beg. Bidirectionallterator end)

О Алгоритм next permutation() изменяет порядок следования элементов в интервале [heg,end) в соответствии со следующей перестановкой.

О Алгоритм prev permutation() изменяет порядок следования элементов в интервале [beg,end) в соответствии с предьщущей перестановкой.

О Оба алгоритма возвращают false, если элементы находятся в нормальном (лексикографическом) порядке, то есть зшорядочены по возрастанию для next permutationO или по убыванию для prev permutation(). Следовательно, для того чтобы перебрать все перестановки, нужно отсортировать элементы (по возрастанию или убыванию) и организовать цикл, который вызывает алгоритм next permutationO или prev permLitation() до тех пор, пока алгоритм возвращает tnje.

Лексикографическая сортировка рассматривается на с. 356.

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

Следующий пример показывает, как при помощи алгоритмов nexLpermutationO и prev permutationO генерируются все перестановки элементов:

algo/perml.cpp #include algostuff.hpp using namespace std:

int mainO (

vector<int> coll:

INSERT ELEMENTS(col 1.1.3): PRINT ELEMENTS(coll. on entry: );

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

* не будут упорядочены

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

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

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

while (next permutation(coll .beginO .coll .endO)) ( PRINT ELEMENTS(coll. ):

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

PRiNTJLEMENTSCcoll . afterward: ):

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

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

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

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

while Cprev permutationCcoll.beginC).col 1.endC))) { PRINT ELEMENTSCcoll . ):

PRiNTJLEMENTSCcoll. now: ):

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

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

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

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

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

while Cprev permutationCcoll.beginO.coll.endC))) ( PRiNTJLEMENTSCcoll. ):

PRINT ELEMENTSCcoll. afterward: ):

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

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 #include <cstdlib> #include algostuff-hpp using namespace std:

class MyRandotn ( public:

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