C++ для начинающих

next_permutation( BidirectionalIterator first,

BidirectionalIterator last );

template class BidirectionalIterator, class Compare

bool

next_permutation( BidirectionalIterator first,

BidirectionalIterator last, class Compare );

next_permutation() берет последовательность, ограниченную диапазоном [first,last), и, считая ее перестановкой, возвращает следующую за ней (о том, как упорядочиваются перестановки, говорилось в разделе 12.5). Если следующей перестановки не существует, алгоритм возвращает false, иначе - true. В первом варианте для определения следующей перестановки используется оператор “меньше” в классе элементов контейнера, а во втором - операция сравнения comp. Последовательные обращения к next_permutation() генерируют все возможные перестановки только в том случае, когда исходная последовательность отсортирована. Если бы в показанной ниже программе мы предварительно не отсортировали строку musil, получив ilmsu, то не удалось бы сгенерировать все перестановки.

#include algorithm

#include vector

#include iostream.h

void print_char( char elem ) { cout elem ; }

void (*ppc)( char ) = print_char;

/* печатается:

ilmsu ilmus ilsmu ilsum ilums ilusm imlsu imlus

imslu imsul imuls imusl islmu islum ismlu ismul

isulm isuml iulms iulsm iumls iumsl iuslm iusml

limsu limus lismu lisum liums liusm lmisu lmius

lmsiu lmsui lmuis lmusi lsimu lsium lsmiu lsmui

lsuim lsumi luims luism lumis lumsi lusim lusmi

milsu milus mislu misul miuls miusl mlisu mlius

mlsiu mlsui mluis mlusi msilu msiul msliu mslui

msuil msuli muils muisl mulis mulsi musil musli

silmu silum simlu simul siulm siuml slimu slium

slmiu slmui sluim slumi smilu smiul smliu smlui

smuil smuli suilm suiml sulim sulmi sumil sumli

uilms uilsm uimls uimsl uislm uisml ulims ulism

ulmis ulmsi ulsim ulsmi umils umisl umlis umlsi

umsil umsli usilm usiml uslim uslmi usmil usmli

*/

int main()

{

vectorchar,allocator vec(5);

// последовательность символов: musil

vec[0] = 'm'; vec[1] = 'u'; vec[2] = 's';

vec[3] = 'i'; vec[4] = 'l';

int cnt = 2;

sort( vec.begin(), vec.end() );

for_each( vec.begin(), vec.end(), ppc ); cout "\t";

// генерируются все перестановки строки "musil"

while( next_permutation( vec.begin(), vec.end()))

{

for_each( vec.begin(), vec.end(), ppc );

cout "\t";

if ( ! ( cnt++ % 8 )) {

cout "\n";

cnt = 1;

}

}

cout "\n\n";

return 0;

}

Алгоритм nth_element()

template class RandomAccessIterator

void

nth_element( RandomAccessIterator first,

RandomAccessIterator nth,

RandomAccessIterator last );

template class RandomAccessIterator, class Compare

void

nth_element( RandomAccessIterator first,

RandomAccessIterator nth,

RandomAccessIterator last, Compare comp );