Permutations
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
در این برنامه همه جایگشتهای سه شیء چاپ شده است. راههای کوتاه تر غیر بازگشتی هم برای این برنامه هست.
داشتنهای جایگشتها کاربردهای مهمی در برنامه نویسی دارد. مثلا اگر بخواهیم حلقههایی تو در تو که تعداد حلقهها ثابت نیست داشته باشیم میتوانیم از جایگشتها استفاده کنیم.