全排列：
從n個(gè)不同元素中任取m（m≤n）個(gè)元素庸追，按照一定的順序排列起來，叫做從n個(gè)不同元素中取出m個(gè)元素的一個(gè)排列涝缝。當(dāng)m=n時(shí)所有的排列情況叫全排列扑庞。
例如：
1、2拒逮、3三個(gè)元素的全排列為：
{1罐氨，2，3}滩援，{1栅隐，3，2}玩徊，{2租悄，1，3}恩袱，{2泣棋，3，1}畔塔，{3潭辈，1，2}澈吨，{3萎胰，2，1}棚辽。
解法1（遞歸）
如下圖：要對(duì)1技竟、2、3屈藐、4進(jìn)行排序榔组，第一個(gè)位置上的元素有四種可能：1或2或3或4，假如已經(jīng)確定了第一個(gè)元素為4联逻，剩下的第二個(gè)位置上可以是1搓扯、2、3包归，很顯然這具有遞歸結(jié)構(gòu)锨推，如果原始要排列的數(shù)組順序?yàn)?、2、3换可、4椎椰，現(xiàn)在只要分別交換1、2沾鳄，1慨飘、3，1译荞、4然后對(duì)剩下的3個(gè)元素進(jìn)行遞歸的排列瓤的。
代碼：
void permute(string str, int k) {
if (k == str.size() - 1) {
cout << str << endl;
} else if (k < str.size() - 1) {
for (int i = k; i < str.size(); i++) {
swap(str[i], str[k]);
permute(str, k + 1);
swap(str[i], str[k]);
}
}
}
void permute(string str) {
if (!str.empty()) {
permute(str, 0);
}
}
遞歸方法會(huì)對(duì)重復(fù)元素進(jìn)行交換比如使用遞歸對(duì){1，1}進(jìn)行全排序會(huì)輸出：{1吞歼，1}圈膏，{1，1}兩個(gè)重復(fù)的結(jié)果篙骡。要在排序的時(shí)候去掉重復(fù)結(jié)果稽坤，可以修改一下代碼如下：
void permute(string str, int k) {
if (k == str.size() - 1) {
cout << str << endl;
} else if (k < str.size() - 1) {
for (int i = k; i < str.size(); i++) {
if (i == k || str[i] != str[k]) {
swap(str[i], str[k]);
permute(str, k + 1);
swap(str[i], str[k]);
}
}
}
}
void permute(string str) {
if (!str.empty()) {
permute(str, 0);
}
}
解法2（字典序法）
字典序法
對(duì)給定的字符集中的字符規(guī)定了一個(gè)先后關(guān)系，在此基礎(chǔ)上規(guī)定兩個(gè)全排列的先后是從左到右逐個(gè)比較對(duì)應(yīng)的字符的先后医增。
列如：對(duì)a、b老虫、c進(jìn)行排序的結(jié)果是{a,b,c}叶骨、{a,c,b}、{b,a,c}祈匙、{b,c,a}忽刽、{c,a,b}、{c,b,a}
字典序法的優(yōu)點(diǎn)是排列的結(jié)果按照順序輸出并且對(duì)于重復(fù)的元素不進(jìn)行重復(fù)排序夺欲。
字典排序法的思想：
例如：對(duì)元素1跪帝，2，3些阅，4進(jìn)行排序伞剑，假設(shè)默認(rèn)的數(shù)組順序?yàn)閧1，2市埋，3黎泣，4}，先輸出第一個(gè)排列：1缤谎、2抒倚、3、4坷澡。然后從右向左找到第一個(gè)非遞增的數(shù)托呕，4，3，因?yàn)?比4小项郊，交換3馅扣、4，并且對(duì)3后面的數(shù)進(jìn)行逆序排列呆抑，第二個(gè)排列為{1岂嗓，2，4鹊碍，3}厌殉，再從右向左3，4侈咕，2公罕，發(fā)現(xiàn)2比4小，交換從右向左第一個(gè)比2大的數(shù)耀销，交換后{1楼眷，3，4熊尉，2}再對(duì)3后面的數(shù)進(jìn)行逆序排列第三個(gè)序列為：{1罐柳，3，2狰住，4}
依次循環(huán)直到數(shù)組成為完全遞減數(shù)組結(jié)束1张吉、2、3催植、4字典排序的最大序列為{4肮蛹，3，2创南，1}伦忠。
代碼：
void permute(string str) {
if (!str.empty()) {
permute(str, 0);
}
}
string permute(string &src, int k) {
sort(src.begin(), src.end());
int len = src.length();
bool end = false;
while (true) {
cout << src << endl;
int index = 0;
int j;
// 從右到左找到第一個(gè)非遞增的元素
for (j = len - 2; j >= 0; j--) {
if (src[j] < src[j + 1]) {
index = j;
break;
} else if (j == 0) {
end = true;
break;
}
}
// 遍歷已經(jīng)結(jié)束
if (end) {
break;
}
// 從右向左找到第一個(gè)比非遞增元素大的元素
for (j = len - 1; j >= 0; j--) {
if (src[j] > src[index]) {
break;
}
}
swap(src[index], src[j]);
reverse(src, index + 1);
}
}
void reverse(string &str, int index) {
int i = index;
int j = str.length() - 1;
while (i < j) {
swap(str[i], str[j]);
i++;
j--;
}
}
轉(zhuǎn)載請(qǐng)注明出處：：https://juejin.cn/post/6897762695689273351
參考文獻(xiàn)：筆試面試算法經(jīng)典--全排列算法-遞歸&字典序?qū)崿F(xiàn)（Java）
