字典序法中，對于數字1、2、3……n的排列，不同排列的先后關系是從左到右逐個比較對應的數字的先后來決定的。例如對于5個數字的排列 12354和12345，排列12345在前，排列12354在后。按照這樣的規定，5個數字的所有的排列中最前面的是12345，最后面的是 54321。

字典序算法如下：
設P是1～n的一個全排列:p=p1p2……pn=p1p2……pj-1pjpj+1……pk-1pkpk+1……pn
1）從排列的右端開始，找出第一個比右邊數字小的數字的序號j（j從左端開始計算），即 j=max{i|pi

實現

遞歸法
遞歸的話就很簡單了，以{1,2,3}為例，它的排列是：
以1開頭，后面接著{2,3}的全排列，
以2開頭，后面接著{1,3}的全排列，
以3開頭，后面接著{1,2}的全排列。
代碼如下：

#include<iostream> #include<algorithm>using namespace std;int arry[3] = { 1,2,3 };void Recursion(int s, int t) {if (s == t)for_each(arry, arry + 3, [](int i) {printf("%d", i); }), printf("\n");else{for (int i = s; i <= t; i++){swap(arry[i], arry[s]);Recursion(s + 1, t);swap(arry[i], arry[s]);}} }int main() {Recursion(0, 2);return 0; }

排序中有重復的情況

#include<iostream> #include<algorithm>using namespace std;int arry[3] = { 1,2,2 };bool IsEqual(int s, int t) {for (int i = s; i < t; i++)if (arry[i] == arry[t])return true;return false; }void Recursion(int s, int t) {if (s == t)for_each(arry, arry + 3, [](int i) {printf("%d", i); }), printf("\n");else{for (int i = s; i <= t; i++){if (!IsEqual(s, i))//不相等才能交換{swap(arry[i], arry[s]);Recursion(s + 1, t);swap(arry[i], arry[s]);}}} }int main() {Recursion(0, 2);return 0; }

利用STL中的next_permutation方法

//簡短的AC代碼。調用了STL的next_permutation函數vector<string> Permutation(string str) {vector<string> answer;if(str.empty())return answer;???????sort(str.begin(),str.end());do{answer.push_back(str);}while(next_permutation(str.begin(),str.end()));return answer; }

字符串字典排序

class Solution { public:vector<string> Permutation(string str) {//可以用遞歸來做vector<string> array;if(str.size()==0)return array;Permutation(array, str, 0);sort(array.begin(), array.end());return array;}void Permutation(vector<string> &array, string str, int begin)//遍歷第begin位的所有可能性{if(begin==str.size()-1)array.push_back(str);for(int i=begin; i<=str.size()-1;i++){if(i!=begin && str[i]==str[begin])//有重復字符時，跳過continue;swap(str[i], str[begin]);//當i==begin時，也要遍歷其后面的所有字符；//當i!=begin時，先交換，使第begin位取到不同的可能字符，再遍歷后面的字符Permutation(array, str, begin+1);//遍歷其后面的所有字符；swap(str[i], str[begin]);//為了防止重復的情況，還需要將begin處的元素重新換回來/*舉例來說“abca”，為什么使用了兩次swap函數交換時是a與b交換，遍歷；交換時是a與c交換，遍歷；（使用一次swap時，是b與c交換）交換時是a與a不交換；*/}} };

參考鏈接：
全排列的實現方法–遞歸&字典序 - 半壺老酒 - 博客頻道 - CSDN.NET

字典序全排列 - zwb8848happy的專欄 - 博客頻道 - CSDN.NET

總結

以上是生活随笔為你收集整理的数据结构之字典序全排列的全部內容，希望文章能夠幫你解決所遇到的問題。

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