STL有全排列函數next_permutation：傳送門

不過還是自己寫寫比較好啊~

自己寫全排列：

#include <iostream> #include <algorithm> using namespace std;const int MAXN = 105; int a[MAXN]; int n,cnt; inline void mySwap(int i,int j) {int temp;temp = a[i];a[i] = a[j];a[j] = temp; } inline void print(int *a) {for(int i = 0; i < n; i++){cout<<a[i]<<" ";}cout<<"\n"; } /* 全排列遞歸寫法（非字典序） 基本思想： 每次固定該序列的某一個數（固定到s位置）， 然后遞歸調用s之后構成的子序列全排列， 直到需要全排列的子序列只有一個數就先打印出整個序列 然后遞歸返回 *///去重 bool check(int cur) {for(int i = cur+1; i < n; i++)//當前交換的與它后面的數有重復，當前位置先不交換{if(a[cur] == a[i])return false;}return true; } /* 解釋“當前交換的與它后面的數有重復，當前位置先不交換”，而為什么不使用當前位置，而讓后面重復的不使用呢？ 這是為了判斷效率，降低判斷難度啊，要判斷 當前序列中這個打算用來交換的數 在當前這個序列 這個數之前 有沒有被使用， 是需要知道 這個子序列的 起始位置的， 因為是遞歸，而每個子序列的起始位置都不同，明顯更不好處理，所以。。。 */ void permutation(int *a,int s) {if(s == n){cnt++;print(a);return;}for(int i = s; i < n; i++){if(check(i)){mySwap(s,i);permutation(a,s+1);mySwap(s,i);}} }/* 全排列非遞歸算法， 并且字典序， 會去重 理解： 因為要字典序，首先就要讓它第一個序列有序（升序）， (對于全是數字來說，全排列字典序就是要讓能組成的數字從小到大排列) 要得到其他序列， 用例子來說明： 序列： 1 2 3 4 1 2 3 4 就是它的全排列的第一個序列 之后肯定要找到最后一對a[i]<a[i+1]，pos = i, 再找pos之后最后一個a[i] > a[pos],k = i 交換pos ，k這兩個位置上的值 a[pos] = 3 a[k] = 4 得到： 1 2 4 3 //這里好像交換后就不需要再做任何操作了，后面也是嗎？ 繼續做下去： a[pos] = 2 a[k] = 3 交換a[pos] 與a[k] 得到： 1 3 4 2 這里明顯不是我們預先想得到的，我們要得到的是：1 3 2 4 我們發現交換后把pos位置之后的序列反轉就是我們想要的 這到是否有通用性，或者是否是正確的做法呢？ 仔細想一想，之前的交換總會使此時pos位置后的子序列， 如果把它看成一個數字，那么它會逐漸變為最大， 但是對于當前pos,后面的序列看成一個數字應該要是最小的， 所以此時pos位置后序列作反轉一定是具有通用性，正確性！！ so：交換之后，一定要反轉pos位置之后的序列 前面有看起來不用反轉，是因為pos位置后的子序列只有一個數，當然看不出要反轉~ 概括總步驟： 1.如果原始序列無序，必須先排序，有序的序列為全排列的第一個序列 2.找最后一對a[i] < a[i+1] ,pos = i 3.pos后找最后一個a[i] > a[pos], k = i 4.交換a[pos],a[k]的值 5.反轉pos之后的序列 6.打印當前序列（這個序列為全排列得到的下一個序列） repeat上述步驟，直到找不到pos */ void permutationTwo(int *a) {sort(a,a+n);//第一個要打印出來cnt++;print(a);while(1){int pos = -1;/*從前往后找最后一個:a[i]<a[i+1],pos = i,現在從后往前找以提高效率，即轉化為第一個:a[i] > a[i-1],pos = i - 1;*/for(int i = n-1; i > 0; i--)//i > 0 防止數組越界{if(a[i] > a[i-1]){pos = i - 1;break;}}if(pos == -1) break;int k = -1;/*找pos之后最后一個a[i] > a[pos],k = i,從后向前找即第一個a[i] > a[pos]，k = i*/for(int i = n-1; i > pos; i--){if(a[i] > a[pos]){k = i;break;}}//交換pos,k兩個位置元素的值mySwap(pos,k);//反轉pos之后元素for(int i = pos+1,j = n-1; i <= j; i++,j--){mySwap(i,j);}cnt++;//打印permutationprint(a);} } int main() {cin>>n;for(int i = 0; i < n; i++){cin>>a[i];}cout<<"permutation:"<<endl;permutation(a,0);cout<<"permutation count = "<<cnt<<endl;cnt = 0;cout<<"permutationTwo:"<<endl;permutationTwo(a);cout<<"permutationTwo count = "<<cnt<<endl;return 0; }

測試結果：

時間復雜度：
遞歸和非遞歸都近似O(n!)
但是非遞歸相對要慢一些，因為它在其他方面，
比如反轉，查找等方面增加了時間消耗。

總結

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

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