一、概述

全排列在很多程序都有應(yīng)用，是一個很常見的算法，常規(guī)的算法是一種遞歸的算法，這種算法的得到基于以下的分析思路。 給定一個具有n個元素的集合（n>=1），要求輸出這個集合中元素的所有可能的排列。

二、遞歸實現(xiàn)

2.1、實例一

例如，如果集合是{a,b,c},那么這個集合中元素的所有排列是{(a,b,c),(a,c,b),(b,a,c),(b,c,a),(c,a,b),(c,b,a)}，顯然，給定n個元素共有n!種不同的排列，如果給定集合是{a,b,c,d}，可以用下面給出的簡單算法產(chǎn)生其所有排列，即集合(a,b,c,d)的所有排列有下面的排列組成：（1）以a開頭后面跟著(b,c,d)的排列（2）以b開頭后面跟著(a,c,d)的排列（3）以c開頭后面跟著(a,b,d)的排列（4）以d開頭后面跟著(a,b,c)的排列，這顯然是一種遞歸的思路，于是我們得到了以下的實現(xiàn)： #include "iostream" using namespace std; void permutation(char* a,int k,int m) { int i,j; if(k == m) { for(i=0;i<=m;i++) cout<<a[i]; cout<<endl; } else { for(j=k;j<=m;j++) { swap(a[j],a[k]); permutation(a,k+1,m); swap(a[j],a[k]); } } } int main(void) { char a[] = "abc"; cout<<a<<"所有全排列的結(jié)果為："<<endl; permutation(a,0,2); system("pause"); return 0; }

2.2、STL實現(xiàn)

有時候遞歸的效率使得我們不得不考慮除此之外的其他實現(xiàn)，很多把遞歸算法轉(zhuǎn)換到非遞歸形式的算法是比較難的，這個時候我們不要忘記了標(biāo)準(zhǔn)模板庫已經(jīng)實現(xiàn)的那些算法，這讓我們非常輕松。STL有一個函數(shù)next_permutation()，它的作用是如果對于一個序列，存在按照字典排序后這個排列的下一個排列，那么就返回true且產(chǎn)生這個排列，否則返回false。注意，為了產(chǎn)生全排列，這個序列要是有序的，也就是說要調(diào)用一次sort。實現(xiàn)很簡單，我們看一下代碼： #include "iostream" #include "algorithm" using namespace std; void permutation(char* str,int length) { sort(str,str+length); do { for(int i=0;i<length;i++) cout<<str[i]; cout<<endl; }while(next_permutation(str,str+length)); } int main(void) { char str[] = "acb"; cout<<str<<"所有全排列的結(jié)果為："<<endl; permutation(str,3); system("pause"); return 0; }

2.3、有一定約束條件的全排列

對數(shù)1，2，3，4，5要實現(xiàn)全排序。要求4必須在3的左邊，其它的數(shù)位置隨意。 思路：首先使用上面的2種方法之一實現(xiàn)全排列，然后對全排列進行篩選，篩選出4在3左邊的排列。 #include "iostream" #include "algorithm" using namespace std; void permutation(int* a,int length) { int i,flag; sort(a,a+length); do { for(i=0;i<length;i++) { if(a[i]==3) flag=1; else if(a[i]==4) //如果3在4的左邊，執(zhí)行完代碼，flag就是2 flag=2; } if(flag==1) //如果4在3的左邊，執(zhí)行完代碼，flag就是1 { for(i=0;i<length;i++) cout<<a[i]; cout<<endl; } }while(next_permutation(a,a+length)); } int main(void) { int i,a[5]; for(i=0;i<5;i++) a[i]=i+1; printf("%d以內(nèi)所有4在3左邊的全排列結(jié)果為：\n",i); permutation(a,5); system("pause"); return 0; }

轉(zhuǎn)自：http://blog.csdn.net/hackbuteer1/article/details/6657435

總結(jié)

以上是生活随笔為你收集整理的全排列递归算法详解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。