Post date: Nov 28, 2013 1:04:21 AM
چاپ همه جایگشت‌های n شیء کار برنامه زیر است. این n شیء را n عدد یعنی عددهای 1 تا n گرفته‌ایم.
#include <conio.h>
#include <iostream>
#include <vector>
using namespace std;
class Permute
{ vector<int> set;
vector<vector<int> > all;
public: void Print()
{
unsigned size = all.size();
for(unsigned i = 0; i < size; i++)
{
unsigned size_i = all[i].size();
for(unsigned j = 0; j < size_i; j++)
cout<< all[i][j] << " ";
cout<< "\n";
}
}
//-------------------------------------------
void Run()
{
unsigned size = set.size();
if(size == 0)
return;
if(size == 1)
{
all.push_back(set);
return;
}
unsigned i = 0; /* sweeper item can be any number between 0 & size - 1 */
vector<int> subset;
for(unsigned j = 0; j < size; j++)
{
if(i != j)
subset.push_back(set[j]);
}
Permute P(subset);
unsigned allsize = P.Size();
for(unsigned k = 0; k < allsize; k++)
{
unsigned size_k = P[k].size();
for(unsigned m = 0; m <= size_k; m++)
{
P[k].insert(P[k].begin() + m,set[i]);
all.push_back(P[k]);
P[k].erase(P[k].begin() + m);
}
}
}
//-------------------------------------------
unsigned Size()
{
return all.size();
}
//-------------------------------------------
vector<int>& operator [](unsigned i)
{
if(Size() <= i)
i = Size() - 1;
return all[i];
}
public: Permute(vector<int> set)
: set(set)
{
Run();
}
};int main()
{ vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3); // v = {1,2,3}
Permute P(v);
P.Print();
_getch();
}Output:
1 2 3
2 1 3
2 3 1
1 3 2
3 1 2
3 2 1
در این برنامه همه جایگشت‌های سه شیء چاپ شده است. راه‌های کوتاه تر غیر بازگشتی هم برای این برنامه هست.
داشتن‌های جایگشت‌ها کاربردهای مهمی در برنامه نویسی دارد. مثلا اگر بخواهیم حلقه‌هایی تو در تو که تعداد حلقه‌ها ثابت نیست داشته باشیم می‌توانیم از جایگشت‌ها استفاده کنیم.