首先，给出算法的思路
设R={r1,r2,...,rn}是要进行排列的n个元素，Ri=R-{ri}。
集合X中元素的全排列记为permutation(X)，(ri)permutation(X)表示在全排列permutation(X)的每一个排列前加上前缀ri得到的排列。
R的全排列可归纳定义如下：
当n=1时，permutation(R)={r},r是集合R中唯一的元素；
当n>1时，permutation(R)由(r1)permutation(R1)，(r2)permutation(R2)，……，(rn)permutation(Rn)构成。
此算法要求待排列的数据是互异的，因为该算法不能检测同种排列是否已经输出，如：
1, 1, 2
那么，全排列期望输出是：
1, 1, 2
1, 2, 1
2, 1, 1
但是该算法的输出：
1, 1, 2
1, 2, 1
2, 1, 1
1, 1, 2
1, 2, 1
2, 1, 1
这是该算法的缺点，也限制了它的适用范围。
程序描述如下：
#include
<
iostream
>
#include
<
algorithm
>
using
namespace
std;
//
递归产生R[k:n]的所有的排列，元素是互异的
template
<
class
Type
>
void
permutation(Type
*
R,
int
k,
int
n)
{
if
(k
==
n)
{
for
(
int
i
=
0
;i
<
n;
++
i)
cout
<<
R[i]
<<
"
\t
"
;
cout
<<
endl;
}
else
for
(
int
i
=
k;i
<
n;
++
i)
{
swap(R[k],R[i]);
permutation(R,k
+
1
,n);
swap(R[k],R[i]);
}
}
还有一种很简单的方法，使用GP中的方法
该算法是STL中的范型算法，当然效果是很好的，不会出现上面的算法的情况。
程序描述如下：
//
使用泛型算法next_permutation()
#include
<
iostream
>
#include
<
vector
>
#include
<
algorithm
>
using
namespace
std;
//
产生R[k:n]的所有的排列
template
<
class
Type
>
void
pernutation(Type
*
R,
int
k,
int
n)
{
vector
<
Type
>
myVec;
int
i,size
=
n
-
k;
for
(i
=
k;i
<
n;i
++
)
myVec.push_back(R[i]);
//
使用next_permutation()函数必须是有序的数据
sort(myVec.begin(),myVec.end());
do
{
for
(i
=
0
;i
<
size;i
++
)
cout
<<
myVec[i]
<<
"
\t
"
;
cout
<<
endl;
}
while
(next_permutation(myVec.begin(),myVec.end()));
}
注：这里的待全排的数据是存在数组或者向量中的。