全排列的生成算法就是對于給定的字符集，用有效的方法將所有可能的全排列無重復(fù)無遺漏地枚舉出來。任何n個字符集的排列都可以與1～n的n個數(shù)字的排列一一對應(yīng)，因此在此就以n個數(shù)字的排列為例說明排列的生成法。
n個字符的全體排列之間存在一個確定的線性順序關(guān)系。所有的排列中除最后一個排列外，都有一個后繼；除第一個排列外，都有一個前驅(qū)。每個排列的后繼都可以從 它 的前驅(qū)經(jīng)過最少的變化而得到，全排列的生成算法就是從第一個排列開始逐個生成所有的排列的方法。
全排列的生成法通常有以下幾種：
字典序法
遞增進位數(shù)制法
遞減進位數(shù)制法
鄰位交換法
遞歸類算法
1.字典序法
字典序法中，對于數(shù)字1、2、3......n的排列，不同排列的先后關(guān)系是從左到右逐個比較對應(yīng)的數(shù)字的先后來決定的。例如對于5個數(shù)字的排列12354和12345，排列12345在前，排列12354在后。按照這樣的規(guī)定，5個數(shù)字的所有的排列中最前面的是12345，最后面的是54321。
字典序算法如下：
設(shè)P是1～n的一個全排列:p=p1p2......pn=p1p2......pj-1pjpj+1......pk-1pkpk+1......pn
1）從排列的右端開始，找出第一個比右邊數(shù)字小的數(shù)字的序號j（j從左端開始計算），即? j=max{i|pi<pi+1}
2）在pj的右邊的數(shù)字中，找出所有比pj大的數(shù)中最小的數(shù)字pk，即 k=max{i|pi>pj}（右邊的數(shù)從右至左是遞增的，因此k是所有大于pj的數(shù)字中序號最大者）
3）對換pi，pk
4）再將pj+1......pk-1pkpk+1pn倒轉(zhuǎn)得到排列p''=p1p2.....pj-1pjpn.....pk+1pkpk-1.....pj+1，這就是排列p的下一個下一個排列。
例如839647521是數(shù)字1～9的一個排列。從它生成下一個排列的步驟如下：
自右至左找出排列中第一個比右邊數(shù)字小的數(shù)字4??????????? 839647521
在該數(shù)字后的數(shù)字中找出比4大的數(shù)中最小的一個5??????? 839647521
將5與4交換??????????????????????????????????????????????????????????????????????????? 839657421
將7421倒轉(zhuǎn)????????????????????????????????????????????????????????????????????????? 839651247
所以839647521的下一個排列是839651247。
2.遞增進位數(shù)制法
在遞增進位制數(shù)法中，從一個排列求另一個排列需要用到中介數(shù)。如果用 ki表示排列p1p2...pi...pn中元素pi的右邊比pi小的數(shù)的個數(shù)，則排列的中介數(shù)就是對應(yīng)的排列k1 ...... ki...... kn-1。
例如排列839647521的中介數(shù)是72642321，7、2、6、......分別是排列中數(shù)字8、3、9、......的右邊比它小的數(shù)字個數(shù)。
中介數(shù)是計算排列的中間環(huán)節(jié)。已知一個排列，要求下一個排列，首先確定其中介數(shù)，一個排列的后繼，其中介數(shù)是原排列中介數(shù)加1，需要注意的是，如果中介數(shù)的末位kn-1+1=2，則要向前進位，一般情形，如果ki+1=n-i+1，則要進位，這就是所謂的遞增進位制。例如排列839647521的中介數(shù)是72642321，則下一個排列的中介數(shù)是67342221+1=67342300（因為1+1=2，所以向前進位，2+1=3，又發(fā)生進位，所以下一個中介數(shù)是67342300）。
得到中介數(shù)后，可根據(jù)它還原對應(yīng)得排列。算法如下：
中介數(shù)k1、k2、......、kn-1的各位數(shù)字順序表示排列中的數(shù)字n、n-1、......、2在排列中距右端的的空位數(shù)，因此，要按k1、k2、......、kn-1的值從右向左確定n、n-1、......、2的位置，并逐個放置在排列中：i放在右起的ki+1位，如果某位已放有數(shù)字，則該位置不算在內(nèi)，最后一個空位放1。
因此從67342300可得到排列849617523，它就是839647521的后一個排列。因為9最先放置，k1=6，9放在右起第7位，空出6個空位，然后是放8，k2=7，8放在右起第8位，但9占用一位，故8應(yīng)放在右起第9位，余類推。
3.遞減進位制數(shù)法
在遞增進位制數(shù)法中，中介數(shù)的最低位是逢2進1，進位頻繁，這是一個缺點。把遞增進位制數(shù)翻轉(zhuǎn),就得到遞減進位制數(shù)。
839647521的中介數(shù)是67342221(k1k2…kn-1)，倒轉(zhuǎn)成為12224376(kn-1…k2k1)，這是遞減進位制數(shù)的中介數(shù)：ki(i=n-1,n-2,…,2)位逢i向ki-1位進1。給定排列p，p的下一個排列的中介數(shù)定義為p的中介數(shù)加1。例如p=839647521，p的中介數(shù)為12224376，p的下一個排列的中介數(shù)為12224376+1=12224377，由此得到p的下一個排列為893647521。
給定中介數(shù)，可用與遞增進位制數(shù)法類似的方法還原出排列。但在遞減進位制數(shù)中，可以不先計算中介數(shù)就直接從一個排列求出下一個排列。具體算法如下：
1）如果p(i)=n且i<>n，則p(i)與p(i-1)交換
2）如果p(n)=n，則找出一個連續(xù)遞減序列9、8、......、i，將其從排列左端刪除，再以相反順序加在排列右端，然后將i-1與左邊的數(shù)字交換
例如p=893647521的下一個排列是983647521。求983647521的下一個排列時，因為9在最左邊且第2位為8，第3位不是7，所以將8和9從小到大排于最右端364752189，再將7與其左方數(shù)字對調(diào)得到983647521的下一個排列是367452189。又例如求987635421的下一個排列，只需要將9876從小到大排到最右端并將5與其左方數(shù)字3對調(diào)，得到534216789。
4.鄰位對換法
鄰位對換法中下一個排列總是上一個排列某相鄰兩位對換得到的。以4個元素的排列為例，將最后的元素4逐次與前面的元素交換，可以生成4個新排列：
1 2 3 4? 1 2 4 3? 1 4 2 3? 4 1 2 3
然后將最后一個排列的末尾的兩個元素交換，再逐次將排頭的4與其后的元素交換，又生成四個新排列：
? 4 1 3 2? 1 4 3 2? 1 3 4 2? 1 3 2 4
再將最后一個排列的末尾的兩個元素交換，將4從后往前移：
3 1 2 4? 3 1 4 2? 3 4 1 2?? 4 3 1 2
如此循環(huán)既可求出全部排列。
5.元素增值法（n進制法）
1）從原始排列p=p1p2......pn開始，第n位加n-1，如果該位的值超過n，則將它除以n，用余數(shù)取代該位，并進位（將第n-1位加1）
2）再按同樣方法處理n-1位，n-2位，......，直至不再發(fā)生進位為止，處理完一個排列就產(chǎn)生了一個新的排列
3）將其中有相同元素的排列去掉
4）當?shù)谝粋€元素的值>n則結(jié)束
以3個數(shù)1、2、3的排列為例：原始排列是1? 2? 3，從它開始，第3個元素是3，3+2=5，5 Mod 3=2，第2個元素是2，2+1=3，所以新排列是1 3 2。通過元素增值，順序產(chǎn)生的排列是：1? 2? 3，1? 3? 2，2? 1? 1，2? 1? 3，2? 2? 2，2? 3? 1，2? 3? 3，3? 1? 2，3? 2? 1
有下劃線的排列中存在重復(fù)元素，丟棄，余下的就是全部排列。
6.遞歸類算法
全排列的生成方法用遞歸方式描述比較簡潔，實現(xiàn)的方法也有多種。
1）回溯法
回溯法通常是構(gòu)造一顆生成樹。以3個元素為例；樹的節(jié)點有個數(shù)據(jù)，可取值是1、2、3。如果某個為0，則表示尚未取值。
初始狀態(tài)是(0，0，0)，第1個元素值可以分別挑選1，2，3，因此擴展出3個子結(jié)點。用相同方法找出這些結(jié)點的第2個元素的可能值，如此反復(fù)進行，一旦出現(xiàn)新結(jié)點的3個數(shù)據(jù)全非零，那就找到了一種全排列方案。當嘗試了所有可能方案，即獲得了問題的解答。
2）遞歸算法
如果用P表示n個元素的排列，而Pi表示不包含元素i的排列，(i)Pi表示在排列Pi前加上前綴i的排列，那么，n個元素的排列可遞歸定義為：
如果n=1，則排列P只有一個元素i
如果n>1，則排列P由排列(i)Pi構(gòu)成（i=1、2、....、n-1）。
根據(jù)定義，容易看出如果已經(jīng)生成了k-1個元素的排列，那么，k個元素的排列可以在每個k-1個元素的排列Pi前添加元素i而生成。例如2個元素的排列是1? 2和2?? 1，對與個元素而言，p1是2? 3和3? 2，在每個排列前加上1即生成1 2 3和1 3 2兩個新排列，p2和p3則是1? 3、3? 1和1? 2、2? 1，按同樣方法可生成新排列2 1 3、2 3 1和3 1 2、3 2 1。
3）循環(huán)移位法
如果已經(jīng)生成了k-1個元素的排列，則在每個排列后添加元素k使之成為k個元素的排列，然后將每個排列循環(huán)左移（右移），每移動一次就產(chǎn)生一個新的排列。
例如2個元素的排列是1 2和2 1。在1 2 后加上3成為新排列1 2 3，將它循環(huán)左移可再生成新排列2 3 1、3 1 2，同樣2 1 可生成新排列2 1 3、1 3 2和3 2 1。
上述算法的程序代碼如下：
#include
<
iostream.h
>
#include
<
time.h
>
const
?maxn
=
100
;
void
?outp(
int
?p[],
int
?n)?????????
//
輸出一個排列????
{
?
int
?i;
?cout
<<
"
?
"
;
?
for
(i
=
1
;i
<=
n;i
++
)
???cout
<<
p[i]
<<
"
?
"
;
??cout
<<
endl;
}
void
?swap(
int
?
&
?x,
int
?
&
?y)
{
?
int
?t
=
x;
?x
=
y;
?y
=
t;
}
void
?dict(
int
?p[],
int
?n)?????????
//
字典序法
{
?
int
?i,j;
?outp(p,n);
?i
=
n
-
1
;
?
while
(i
>
0
)
?
{
??
if
?(p[i]
<
p[i
+
1
])
??
{
???
for
(j
=
n;j
>=
i
+
1
;j
--
)
????
if
(p[i]
<=
p[j])?
break
;
???swap(p[i],p[j]);
???
for
(j
=
n;j
>=
1
;j
--
)
???
{
????i
+=
1
;
????
if
?(i
>=
j)?
break
;
????swap(p[i],p[j]);
???}
???outp(p,n);
???i
=
n;
??}
??i
-=
1
;
?}
;
}
bool
?midn(
int
?m[],
int
?n)
{
?
int
?k
=
n
-
1
;
?
while
(
1
)
?
{
??m[k]
+=
1
;
??
if
(m[k]
<
n
-
k
+
1
)
break
;
??m[k]
=
0
;
??k
-=
1
;
?}
?
int
?s
=
0
;
?
bool
?b
=
false
;
?
for
(?k
=
1
;k
<=
n;)
??s
+=
m[k
++
];
?
if
(s
==
0
)?b
=
true
;
?
return
?b;
}
void
?incr(
int
?p[],
int
?n)
{
?
int
?m[maxn];
?
int
?i,j,a;
?
for
(i
=
1
;i
<=
n;)
??m[i
++
]
=
0
;
?
while
(i
>
0
)
?
{
??
for
(i
=
1
;i
<=
n;)
???p[i
++
]
=
0
;
??
for
(i
=
1
;i
<=
n;i
++
)
??
{
???a
=
m[i]
+
1
;
???j
=
n;
???
while
(j
>
0
)
???
{
????
if
(p[j]
==
0
)
????
{
?????a
-=
1
;
?????
if
(a
==
0
)?
break
;
????}
????j
-=
1
;
???}
???p[j]
=
n
-
i
+
1
;
??}
??outp(p,n);
??
if
?(midn(m,n)
==
true
)?
break
;??
?}
}
void
?degr(
int
?p[],
int
?n)
{
?
int
?i,j;
?
while
(
1
)
?
{
??outp(p,n);
??
if
(p[
1
]
!=
n)
??
{
???i
=
0
;
???
while
(p[
++
i]
!=
n);????
???swap(p[i],p[i
-
1
]);
??}
??
else
??
{
???i
=
1
;
???
while
(i
<
n)
???
{
????
if
(p[i]
!=
p[i
+
1
]
+
1
)?
break
;
????i
+=
1
;
???}
???
if
(i
==
n)
break
;??????
???j
=
i;
???
while
(p[i]
!=
p[j]
-
1
)
????i
+=
1
;
???swap(p[i],p[i
-
1
]);
???
for
(i
=
1
;i
<=
n
-
j;)
????p[i
++
]
=
p[i
+
j];
???
for
?(i
=
1
;i
<=
j;i
++
)
????p[n
-
i
+
1
]?
=
n
-
i
+
1
;???
??}
?}
}
void
?conv(
int
?p[],
int
?n)
{
?
long
?m
=
1
;
?
for
(
int
?i
=
3
;i
<
n;)
??m
=
m
*
i
++
;
?
for
(i
=
1
;i
<
m;i
++
)
?
{
??outp(p,n);
??
for
(
int
?j
=
n;j
>
1
;j
--
)
??
{
???swap(p[j],p[j
-
1
]);
???outp(p,n);
??}
????????swap(p[n],p[n
-
1
]);
??outp(p,n);
??
for
(j
=
1
;j
<
n;j
++
)
??
{
???swap(p[j],p[j
+
1
]);
????????????outp(p,n);
??}
????????swap(p[
1
],p[
2
]);
?}
}
bool
?test(
int
?p[],?
int
?n)
{
?
bool
?b
=
false
;
?
for
(
int
?i
=
1
;i
<=
n;i
++
)
??
for
(
int
?j
=
i
+
1
;j
<=
n;j
++
)
???
if
(p[i]
==
p[j])?
???
{
????b
=
true
;
????
break
;
???}
????
return
?b;
}
void
?Nnum(
int
?p[],
int
?n)
{
?
while
(n
>
0
)
?
{
??
if
?(test(p,n)
==
false
)?outp(p,n);
??p[n]
+=
n
-
1
;?????????????????????????????
????????
for
(
int
?j
=
n;j
>
1
;j
--
)
??
{
??????????
if
(p[j]
>
n)
????
{
?????p[j]
%=
n;?????????????????????????????
??????????????p[j
-
1
]
+=
1
;?????????????????????
??????????????
if
(p[
1
]
>
n)
?????
{
??????n
=
0
;
??????
break
;
?????}
????}
??}
????????????????????????????????
?}
}
void
?recu(
int
?p[],
int
?n,
int
?k)
{
?
if
(k
==
n)?
??outp?(p,n);
?
else
?
{
??
for
(
int
?i
=
k;i
<=
n;i
++
)
????????
{
???swap?(p[k],p[i]);
???recu(p,?n,k
+
1
);
???swap?(p[k],p[i]);?
??}
????}
}
void
?cyc(
int
?p[],
int
?n,
int
?k)
{
?
if
?(k
>
n)
??outp(p,n);
?
else
?
{
??
for
(
int
?i
=
0
;i
<
k;i
++
)
??
{
???
int
?t
=
p[
1
];
???
for
(
int
?j
=
2
;j
<=
k;j
++
)
????p[j
-
1
]
=
p[j];
????????????p[k]
=
t;
???cyc(p,n,k
+
1
);
????????}
?}
}
void
?remo(
int
?p[],
int
?n,
int
?k)
{
?
bool
?b;
?
if
?(k
>
n)
??outp?(p,n);
?
else
?
{
???????
for
(
int
?i
=
1
;i
<=
n;i
++
)
????
{
?????b
=
false
;
?????p[k]
=
i;??????????????????
???????????
for
(
int
?j
=
1
;j
<
k;j
++
)
??????
if
(i
==
p[j])
????
{
??????b
=
true
;
??????
break
;
????}
???
if
(b
==
false
)?remo(p,n,k
+
1
);?????
????}
????}
}
void
?main()
{
?
int
?i,j,m;
?
int
?p[maxn];
?
int
?n;
?clock_t?start,finish;
?cout
<<
"
輸入排列元素總數(shù)?n=
"
;
?cin
>>
n;
?
for
(i
=
1
;i
<=
n;i
++
)
??p[i]
=
i;?
?cout
<<
"
1——字典序法
"
<<
endl;
?cout
<<
"
2——遞增進位數(shù)制法
"
<<
endl;
?cout
<<
"
3——遞減進位數(shù)制法
"
<<
endl;
?cout
<<
"
4——鄰位交換法
"
<<
endl;
?cout
<<
"
5——n進制數(shù)法
"
<<
endl;
?cout
<<
"
6——遞歸生成法
"
<<
endl;
?cout
<<
"
7——循環(huán)移位法
"
<<
endl;
?cout
<<
"
8——回溯法
"
<<
endl;
?cout
<<
"
請選擇:?
"
;
?cin
>>
m;
?start
=
clock();
?
switch
?(m)
?
{
????
case
?
1
:dict(p,n);
break
;
????
case
?
2
:incr(p,n);
break
;?
???????
case
?
3
:degr(p,n);
break
;??
????
case
?
4
:conv(p,n);
break
;
???????
case
?
5
:Nnum(p,n);
break
;?
???????
case
?
6
:recu(p,n,
1
);
break
;
????
case
?
7
:cyc(p,n,
1
);
break
;????
???????
case
?
8
:remo(p,n,
1
);
?}
?finish
=
clock();
?cout
<<
"
程序執(zhí)行時間：
"
??
<<
(
double
)(finish
-
start)
/
CLOCKS_PER_SEC
<<
"
秒
"
<<
endl;
}
reference :
http://course.zjnu.cn/quyt/bbs/ftbbs.asp?id=115?void?sort(char?s[]){};
?char?p[]?="????";
?void?perm(char?s[],?int?i,?int?n)
?{
??????int?j;
??????char?temp;
??????printf("perm?i=%d?????????s=%s??p=%s\n",i,s,p);
??????for(j=0;j<n;++j)
??????{
??????????if(j!=0?&&?s[j]==s[j-1]);
??????????else?if(s[j]!='@')
??????????{
??????????????p[i]=s[j];
??????????????s[j]='@';
??????????????if(i==n-1)
??????????????{
??????????????????p[n]='\0';
??????????????????printf("===============output?:?%s\n\n",?p);
??????????????}
??????????????else
??????????????{
??????????????????printf("?????i=%d??j=%d????s=%s??p=%s\n",i,j,s,p);
??????????????????perm(s,i+1,n);
??????????????}
??????????????s[j]=p[i];
??????????}
??????}
?}
?void?Test31()?
?{
??????char?s[]=?"112";
??????sort(s);
??????perm(s,0,strlen(s));
??}