الگوریتم ها

همانند دربرگیرنده ها در کتابخانه $STL$ تعدادی از الگوریتم های پرکابرد نوشته شده است. برای استفاده از آن ها ابتدا باید کتابخانه زیر را $include$ کنید.

#include <algorithm>

حال به بررسی برخی از آنان میپردازیم

با استفاده از این تابع میتوانیم عناصر یک آرایه یا یک $vector$ را مرتب کنیم. توجه کنید که برای اینکه بتوان آن ها را مرتب کرد نیاز است که کوچکتر بودن برای آن $type$ تعریف شده باشد. برای $type$ های پیشفرض این رابطه تعریف شده است. همچنین میتوان از تابعی دلخواه برای مقایسه استفاده کرد که آن را باید به عنوان پارامتر سوم بدهیم.

sort(startPointer,endPointer) // endPointer is not included                
sort(startPointer,endPointer,compareFunction)

توجه کنید که خود $endPointer$ شامل بازه مرتب سازی نمیشود. به عنوان مثال :

int A[10];
vector<int> V;
sort(A+2,A+5); // sorts the element number 2 to element number 4 (2 and 4 included)
sort(V.begin(),V.end()) // sorts All of Vector v

حال فرض کنید میخواهیم تابعی بنویسیم که به وسیله عناصر را صعودی مرتب کنیم :

bool cmp(int a,int b){
     return (a>b);
}
sort(V.begin(),V.end(),cmp);

این تابع یک بازه از آرایه یا $vector$ را با مقدار داده شده پر میکند. معمولا برای $0$ کردن یا مقدار اولیه دادن به آرایه یا $vector$ کاربرد دارد.

// Format
fill(startPointer,endPointer,value);
// Example
fill(A,A+n,0);

این تابع یک بازه از آرایه یا $vector$ را برعکس میکند.

// Format
reverse(startPointer,endPointer);
// Example
reverse(S.begin(),S.end());

این تابع روی یک بازه مرتب شده اعمال شده و عناصر آن را $unique$ میکند یعنی از هر عنصر یکی را نگه داشته و باقی تکرار هارا در انتها میگذارد و اشاره گر به انتهای عناصر یکتا را بازمیگردند. توجه کنید که عنصری که این اشاره گر به آن اشاره میکند اولین عنصر بعد از بازه یکتا شده است.

// Format
unique(startPointer,endPointer);
// Example
vector<int> v;
sort(v.begin(),v.end());
v.resize(unique(v.begin(),v.end())-v.begin());

با استفاده ازین تابع میتوانید روی یک بازه $sort$ شده $binarysearch$ انجام داده و به دنبال مکان یک مقدار خاص بگردید.

• عملکرد $lowerBound$ : اشاره گر به اولین جایی که از مقدار داده شده بیشتر یا مساوی است.
• عملکرد $upperBound$ : اشاره گر به اولین جایی که از مقدار داده شده بیشتر است.

// Format
lower_bound(startPointer,endPointer,value);
upper_bound(startPointer,endPointer,value);
// Example
lower_bound(v.begin(),v.end(),2);

با استفاده از این تابع میتوانید جایگشت بعدی یا قبلی یک بازه را حساب کنید. این تابع یک مقدار $boolean$ برمیگرداند که در صورتی که برای $nextPermutation$ روی بزرگترین جایگشت اعمال شود $false$ و در غیر اینصورت $true$ است و برای $prevPermutation$ در صورتی که روی کوچکترین جایگشت اعمال شود $false$ و در غیر ایصورت $true$ است.

// Format
next_permutation(startPointer,endPointer);
prev_permutation(startPointer,endPointer);

میخواهیم برنامه ای بنویسیم که تمام جایگشت ها ${1,2,...n}$ را چاپ کند

permuation.cpp

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int MAX_N=100*1000;
void show(const vector<int>& V){
	for(int i=0;i<(int)V.size();i++)
		cout<<V[i]<<" ";
	cout<<endl;
}
vector<int> P;
int main()
{
	int n;
	cin >> n;
	for(int i=1;i<=n;i++)
		P.push_back(i);
	sort(P.begin(),P.end());  // not needed here but remember to do it !
	do{
		show(P);
	}while(next_permutation(P.begin(),P.end()));
	return 0;
}