n болып келетін тізбек үшін мұндай қайта орналастыру- 393

393
лар саны 
n! (1*2*...*n) 
болады. 
next_permutation
алгоритмі кезекті 
қайта орналастыруды лексикографиялық тəртіппен, ал 
prev_permutation
алгоритмі бұрынғы орналастыруды жүзеге асырады. Егер келесі орналасты-
ру бар болатын болса, алгоритмдер 
true
бульдік мəнін, кері жағдайда 
false
мəнін қайтарады.
template
 
bool next_permutation(Bi fi rst, Bi last);
 
template
 
bool next_permutation(Bi fi rst, Bi last, Compare comp); 
template
 
bool prev_permutation(Bi fi rst, Bi last); 
template
 
bool prev_permutation(Bi fi rst, Bi last, Compare comp); 
Мысал:
#include  
#include  
using namespace std; 
int main(){
 
const int m = 3;
 
int a[m]={1, 4, 2}, b[m];
 int 
i;
 
copy(a, a + m, b);
 
cout << " next_permutation(a, a + m):" << endl;
 
while (next_permutation(a, a + m)){
 
for (i = 0; i < m; i++) cout << a[i] << " "; 
 
cout << endl;} 
 
cout << " prev_permutation(b, b + m):" << endl; 
while (prev_permutation(b, b + m)){
 
for (i = 0; i < m; i++) cout << b[i] << " "; 
 
cout << endl;} 
 return 
0;
}
Программа жұмысының нəтижесі:
next_permutation(a, a + m): 
2 1 4 
2 4 1 
4 1 2 
4 2 1
prev_permutation(b, b + m): 
1 2 4
26-1140

394
nth_element
Алгоритм жиымды ішінара сұрыптау əрекетін орындайды. Алгоритмнің 
орындалуынан кейін 
nth
итераторы арқылы берілген элементтің мəні толық 
сұрыптаудан кейінгімен бірдей болады, яғни осы позициядан солға қарай 
орналасқан элементтер одан кіші, оңға қарай орналасқандары одан үлкен 
болады.
template
 
void nth_element(Ran fi rst, Ran nth, Ran last);
template
 
void nth_element(Ran fi rst, Ran nth, Ran last, 
 
Compare comp);
partial_sort, partial_s ort_copy
partial_sort
алгоритмі де тізбекті ішінара сұрыптау əрекетін орындай-
ды. Алгоритм орындалған соң 
fi rst 
жəне 
middle
аралығындағы элементтер 
толық сұрыптаудан кейінгідей тəртіппен орналасады.
partial_sort_copy
алгоритмі тізбектің көшірмесімен дəл осындай 
əрекеттерді орындайды. 
template
 
void partial_sort(Ran fi rst, Ran middle, Ran last); 
template
 
void partial_sort(Ran fi rst, Ran middle, Ran last, 
 
Compare comp); 
template
 
Ran partial_sort_copy(In fi rst, In last, 
 
Ran result_fi rst, Ran result_last);
template 
 
Ran partial_sort_copy(In fi rst, In last,
 
Ran result_fi rst, Ran result_last, Compare comp);
Ішінара сұрыптау біз үшін бірнеше ең кіші немесе ең үлкен мəндер ғана 
маңызды болған жағдайларда, уақытты үнемдейді.

жүктеу/скачать 3,66 Mb.

Достарыңызбен бөлісу: