首先，給出算法的思路
設(shè)R={r1,r2,...,rn}是要進(jìn)行排列的n個(gè)元素，Ri=R-{ri}。
集合X中元素的全排列記為permutation(X)，(ri)permutation(X)表示在全排列permutation(X)的每一個(gè)排列前加上前綴ri得到的排列。
R的全排列可歸納定義如下：
當(dāng)n=1時(shí)，permutation(R)={r},r是集合R中唯一的元素；
當(dāng)n>1時(shí)，permutation(R)由(r1)permutation(R1)，(r2)permutation(R2)，……，(rn)permutation(Rn)構(gòu)成。
此算法要求待排列的數(shù)據(jù)是互異的，因?yàn)樵撍惴ú荒軝z測同種排列是否已經(jīng)輸出，如：
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
這是該算法的缺點(diǎn)，也限制了它的適用范圍。
程序描述如下：
#include?
<
iostream
>
#include?
<
algorithm
>
?
using
?
namespace
?std;?
//
?遞歸產(chǎn)生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中的范型算法，當(dāng)然效果是很好的，不會出現(xiàn)上面的算法的情況。
程序描述如下：
//
?使用泛型算法next_permutation()
#include?
<
iostream
>
#include?
<
vector
>
#include?
<
algorithm
>
?
using
?
namespace
?std;?
//
?產(chǎn)生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()函數(shù)必須是有序的數(shù)據(jù)
?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()));
}
注：這里的待全排的數(shù)據(jù)是存在數(shù)組或者向量中的。