در پست های قبل “الگوریتم جایگشت های یک رشته یا مجموعه با ++C” در مورد پیدا کردن جایگشت های یک آرایه صحبت کرده بودیم ولی آن روش روشی بازگشتی بود که از لحاظ سرعت و حافظه به دلیل ساختار بازگشتی اش کمی مشکل داشت ولی امروز الگوریتم سریعی تر را به شما معرفی می کنیم . همین طور این الگوریتم در صورت وجود عضو تکراری جایگشت تکراری ایجاد نمی کند.

یک از بهترین الگوریتم ها برای پیدا کردن جایگشت های المنت های یک آرایه استفاده از الگوریتم Next Lexicographical  Permutation است. این الگوریتم یک آرایه را می گیرد و جایگشت بعدی آن آرایه را می دهد بطوری که جایگشت جدید در بین همه جایگشت های ممکن اولین جایگشتی است که ظاهر می شود به طور مثال جایگشت های عدد هایی یک دو و سه به شکل زیر است:

۱ ۲ ۳

۱ ۳ ۲

۲ ۱ ۳

۲ ۳ ۱

۳ ۱ ۲

۳ ۲ ۱

   فرض کنید آرایه ما   ۳ ۱ ۲ است جایگشت بعدی آن ۱ ۳ ۲ است زیرا از بین جایگشت هایی که از ۲۱۳ بزرگ تر هستند ۲۳۱ کوچک ترین آن ها است .

الگوریتم جایگشت های بعدی Next Lexicographical Permutation هم جایگشت بعدی یک آرایه ورودی را تولید می کند.

الگوریتم آن به این صورت است (در تصویر زیر مراحل آمده است)‌:

۱ – ابتدا بزرگ ترین زیر suffix نزولی را از سمت راست آرایه پیدا می کنیم که در ورودی شکل زیر suffix مورد نظر ما

قسمت ۵۱۰ است به عضو قبل از شروع suffix که در شکل عدد دو است pivot می گویند.

۲ – در suffix کوچک ترین المنتی که از pivot بزرگ تر است را پیدا می کنیم و جای آن و pivot را عوض می کنیم.

۳ – با این کار کوچک ترین عضو ممکن را که باعث افزایش مقدار prefix می شد را به prefix منتقل کردیم. در این مرحله suffix را صعوی مرتب می کنیم ولی از آنجایی که خود suffix در حال حاضر نزولی است کافی است آن را برعکس کنیم به همین خاطر مرتب سازی نیازی نیست.

۴ – کوچک ترین عضو ممکن suffix را به prefix منتقل کردیم و suffix را صعودی مرتب کردیم در نتیجه آرایه ای که به دست آمده جایگشت بعدی آرایه ی اولیه است .

کد پیدا کردن جایگشت بعدی ( Next Lexicographical  Permutation ) به زبان سی پلاس پلاس C++ :

template<class T>
bool NextLexicographicalPermutation(vector<T> &arr)
{
	if (arr.size() == 0)
	{
		return false;
	}

	vector<T> ::iterator i = arr.end() - 1;

	//finding bigest increasing suffix
	while (i > arr.begin() && *(i - 1) >= *i)
	{
		i--;
	}

	//if bigest increasing sufix be equal main array then 
	//array does not have any next permutation
	if (i == arr.begin())
	{
		return false;
	}

	
	vector<T> ::iterator j = arr.end() - 1;
	
	//find smallest number that greater than pivot 
	while (*j < *(i - 1) )
	{
		j--;
	}

	//swap pivot
	iter_swap(j, i - 1);
	
	//reverse suffix
	reverse(i, arr.end());

	return true;
}

تا اینجا جایگشت بعدی یک آرایه را توانستیم پیدا کنیم . همان طور که در تابع بالا می بینید در صورت وجود جایگشت بعدی آن را تولید می کند و مقدار true را بر می گرداند و صورتی که آرایه در حالت ماکزیمم خود باشد و جایگشت بعدی وجود نداشته باشد false را بر می گرداند. هزینه ی این الگوریتم (O(n است.

حالا می خواهیم یک تابع بنویسیم که تمام جایگشت های یک آرایه را تولید کند. برای این کار می گوییم ابتدا آرایه را سورت کن (اگر مرتب نکنیم آرایه را آنگاه جایگشت هایی که کوچک تر از حالت فعلی هستند  پیدا نمی شوند زیرا این الگوریتم جایگشت ها بعدی یک آرایه را می دهد نه جایگشت های قبلی) بعد از آن تا زمانی که تابع تولید جایگشت false نشده است جایگشت های بعدی آن را تولید کن. هزینه ی این الگوریتم  (!O(n* n است.

کد سی پلاس پلاس (c++) تولید همه ی جایگشت های (permutation) یک آرایه را همراه تست آن بر روی دو آرایه ی متفاوت را در زیر می بینید:

// Next lexicographical permutation.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
#include <string>

using namespace std;

template<class T>
bool NextLexicographicalPermutation(vector<T> &arr)
{
	if (arr.size() == 0)
	{
		return false;
	}

	vector<T> ::iterator i = arr.end() - 1;

	//finding bigest increasing suffix
	while (i > arr.begin() && *(i - 1) >= *i)
	{
		i--;
	}

	//if bigest increasing sufix be equal main array then 
	//array does not have any next permutation
	if (i == arr.begin())
	{
		return false;
	}

	
	vector<T> ::iterator j = arr.end() - 1;
	
	//find smallest number that greater than pivot 
	while (*j < *(i - 1) )
	{
		j--;
	}

	//swap pivot
	iter_swap(j, i - 1);
	
	//reverse suffix
	reverse(i, arr.end());

	return true;
}


//print all permutatoin 
template<class T>
void printAllPermutation(vector<T> arr)
{
	vector<T> temparr(arr.begin(), arr.end());

	//if  vector not be sorted then sort it 
	if (!is_sorted(temparr.begin(), temparr.end(), [](T a, T b){if (a < b){ return true; }else{return false;}}))
	{
		sort(temparr.begin(), temparr.end());
	}

	do
	{
		for_each(temparr.begin(), temparr.end(), [](T i){cout << i; });
		cout << endl;
	} while (NextLexicographicalPermutation(temparr));
}

int main()
{
	int arr[] = { 2, 1, 3 };
	vector<int> myVec(arr, arr + 3);
	printAllPermutation(myVec);
	
	cout << endl;

	char arr1[] = { 'B', 'A', 'C'};
	vector<char> myVec1(arr1, arr1 + 3);
	printAllPermutation(myVec1);

	return 0;
}

در تصویر زیر خروجی برنامه ی بالا را می بینید:

اگر کد این برنامه را با زبانی دیگر نوشته اید آن را برایمان ارسال کنید تا به این پست اضافه اش کنیم.