全排列問題：

給定n個字符{r1,r2,…,rn}，要求生成這n個字符的全排序

?

算法思想：

設R={r1,r2,…,rn}是要進行排列的n個元素，Ri=R-{ri}。
集合X中元素的全排列記為perm(X)。
(ri)perm(X)表示在全排列perm(X)的每一個排列前加上前綴得到的排列。

R的全排列可歸納定義如下：
（1）當n=1時，perm(R)=(r)，其中r是集合R中唯一的元素；
（2）當n>1時，perm(R)由(r1)perm(R1)，(r2)perm(R2)，…，(rn)perm(Rn)構成。

?

算法分析

???????? 1、假設有兩個數 1，2，他們的全排列是 1，2和2，1，即以1開頭的2的全排列和以2開頭的1的全排列，而1個數的全排列是其本身，即定義（1）部分。

???????? 2、假設有三個數1，2，3，他們的全排列是 1，2，3；1，3，2；2，1，3；2，3，1；3，1，2；3，2，1六組，即定義（2）部分。

???????? 3、定義（2）部分可以理解為：將整個數列中每一個數分別與第一個數交換后加其他數的全排列，因此每次都是處理后n-1個數的全排列

???????? 4、123的全排列：首先遍歷所有元素，然后把遍歷到的每一個元素和第一個元素交換：

（1）1和1交換還是1，那么就有了1，（2，3）

（2）同理，2，3和第一個交換后有了2，（1，3）和3，（1，2）共3組

（3）交換完了后要交換回來，因為后面交換都是在原來的數列1，2，3的基礎上交換的，所以在排列前要交換一次，排列后還要交換一次（還原）

（4）檢查每組除了第一個元素之外剩余的元素，如果元素的個數是2，那么就對剩下的元素進行全排列（遞歸）。

（5）1（2，3）按第1~4步得到1，2，3；1，3，2

5、為什么要交換兩次？會漏掉很多組合

?

執行步驟

???????? 求n個元素a1,a2 ….an的全排列:由排列組合的知識可知，n個元素的全排列有n!種=n*(n-1)!種=n*(n-1)*(n-2)!種=….

???????? 分析 ：? n=1??? ? out: a1

??????????? n=2??????????? out:? a1,a2

??????????????????????????????????????????????????????? a2,a1

??????????????????????????? n=3??????????? out:? a1,a2,a3

??????????????????????????????????????????????????????? a1,a3,a2

??????????????????????????????????????????????????????? a2,a1,a3

??????????????????????????????????????????????????????? a2,a3,a1

??????????????????????????????????????????????????????? a3,a1,a2

??????????????????????????????????????????????????????? a3,a2,a1

?? 上述步驟可以用循環執行“交換位置，后跟剩余的序列的全排列”；對剩余的序列再次使用該方法，直至沒有剩余序列（只有一個元素）

?

#include<iostream>
#include <math.h>
using namespace std;
void perm(char ch[],int s,int t)
{
?int i;
?if(s==t)
?{
??for(i=0;i<=t;i++)
???cout<<ch[i];
??cout<<endl;
?}
?else
?{
??for(i=s;i<=t;i++)
??{
???swap(ch[i],ch[s]);
???perm(ch,s+1,t);
???swap(ch[i],ch[s]);
??}
?}
}
int main()
{
?int i,n,m;
?char ch[1000];
?cin>>n;
?while(n--)
?{
??cin>>m;
??for(i=0;i<m;i++)
???cin>>ch[i];
??perm(ch,0,m-1);
??if(n) cout<<endl;
?}
}

總結

以上是生活随笔為你收集整理的分治法求全排列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。