前言

next_permutation/prev_permutation是C++ STL中的一種實(shí)用算法;

功能是： 以迭代器的方式，將一個(gè)容器內(nèi)容改變?yōu)樗南乱粋€(gè)(或prev上一個(gè))全排列組合;

next_permutation的使用

假設(shè)需要將字符串a(chǎn)bcd的全排列依次打印，我們可以用next_permutation函數(shù)方便操作:

使用方法:

1.一般先sort成升序;(prev_permutation倒著全排列使用規(guī)則相反)

2.然后再do while配合調(diào)用全排列，循環(huán)輸出，直到排列情況全部輸出 返回false;

運(yùn)行結(jié)果:

實(shí)現(xiàn)全排列的兩種算法

當(dāng)然僅僅只會(huì)用沒(méi)有什么困哪的，如果面試官突然問(wèn)你STL中這個(gè)全排列算法咋實(shí)現(xiàn)的呢？

1. 遞歸法(全排列方便理解記憶的方法，作為備用方法)

如果上面全排列，突然腦袋斷片了，或者說(shuō)考試中不讓用封裝好的庫(kù)函數(shù);

為了不至于連個(gè)全排列的思想都不會(huì)，可以用用相對(duì)好理解的遞歸法全排列：

算法思想:(遞歸問(wèn)題：按規(guī)則處理一個(gè)過(guò)程，剩下的過(guò)程是相同的處理方式，那么就可以進(jìn)行函數(shù)遞歸調(diào)用)

1.從集合中依次選出每一個(gè)元素，作為排列的第一個(gè)元素；

2.然后**對(duì)剩余的元素(第一個(gè)元素之后的)進(jìn)行 同樣操作 **;

如此遞歸處理，從而得到所有元素的全排列。

eg：

以對(duì)字符串a(chǎn)bc進(jìn)行全排列為例，我們可以這么做：以abc為例

• 固定a，遞歸求后面bc的排列：求好: abc，acb后，b交換到第一位置，得到bac，如下固定b遞歸b后面的排列：
• 固定b，求后面ac的排列：bac，bca，求好后，c交換到第一位置，得到cba，如下固定c遞歸c后面的排列：
• 固定c，求后面ba的排列：cba，cab;結(jié)束 一共a，b，c分別當(dāng)?shù)谝粋€(gè)元素進(jìn)行了全排列，算法結(jié)束;

（注意：1. 每次交換下一個(gè)位置的時(shí)候，需要swap換回來(lái)，保證原始序列，再交換下一個(gè)位置的字母去第一個(gè)位置。2. 需要考慮有重復(fù)相同且挨著的數(shù)字情況，此時(shí)需要剪枝）

遞歸比較抽象，可以用簡(jiǎn)單地例子abc在紙上模擬畫(huà)一下好理解;

實(shí)現(xiàn)代碼(無(wú)重復(fù)元素情況)

#include<iostream>
#include<vector>
using namespace std;

//dfs實(shí)現(xiàn)全排列(無(wú)重復(fù)元素情況)
void dfs(string &s, int l, int r)
{
	if (l == r) {//遞歸終止，當(dāng)前s可以輸出了，已經(jīng)是某一輪的完整排列，不能再排列了
		cout<<s<<endl;
		return;
	}

	for (int i = l; i < r; i++) {
        
            swap(s[l],s[i]);
			dfs(s,l+1,r);//遞歸
			swap(s[l], s[i]);//進(jìn)行下一輪的swap dfs，需要先swap換回來(lái)原來(lái)的位置！否則會(huì)出現(xiàn)重復(fù)排列!
		
	}
}


int main()
{
	string s = "abcd";
    //sort(s.begin(),s.end())//sort一下，再配合dfs算法，可以實(shí)現(xiàn)按照字典序處理
    int len = s.size();
	dfs(s,0,len);
	return 0;
}

運(yùn)行結(jié)果:

有重復(fù)元素情況

這種情況需要對(duì)代碼做一個(gè)優(yōu)化，不然的話(huà)按照上面的算法，會(huì)出現(xiàn)重復(fù)數(shù)字的重復(fù)排列情況;

優(yōu)化很簡(jiǎn)單:

如果某個(gè)數(shù)字在之前的排列被換到首位置進(jìn)行排列過(guò)，那本次交換就不進(jìn)行;（其次，當(dāng)dfs首次交換i==l的時(shí)候，即便出現(xiàn)過(guò)也需要進(jìn)行);

整合一下就是if(i==l || s[i]沒(méi)出現(xiàn)) -->進(jìn)行交換）

代碼:

#include<iostream>
#include<algorithm>
#include<set>
using namespace std;

//dfs實(shí)現(xiàn)全排列(含重復(fù)元素情況)
void dfs(string &s, int l, int r)
{
	if (l == r) {
		cout<<s<<endl;
		return;
	}
	set<char>st;//檢測(cè)重復(fù)的set
	for (int i = l; i < r; i++) {
		if (i == l || st.find(s[i])==st.end()) {//防止后續(xù)進(jìn)行重復(fù)排列
			st.insert(s[i]);//滿(mǎn)足  記錄這個(gè)字符 

			swap(s[l], s[i]);
			dfs(s, l + 1, r);
			swap(s[l], s[i]);
		}
	}
}


int main()
{
	string s = "aba";
	int len = s.size();
	dfs(s,0,len);
	return 0;
}

2. 迭代法(next_permutation底層原理)

比較抽象，難以理解，根據(jù)個(gè)人情況來(lái)理解;

一個(gè)全排列可看做一個(gè)字符串，字符串可有前綴、后綴。

規(guī)定: 生成給定全排列的下一個(gè)排列–> 所謂一個(gè)字符串的下一個(gè)排列，就是這個(gè)個(gè)字符串變化限制在盡可能短的后綴上，變化后的那個(gè)字符串; 這就要求這一個(gè)與下

一個(gè)有盡可能長(zhǎng)的共同前綴;變化限制在盡可能短的后綴上

eg:

839647521是1—9的排列。1—9的排列最前面的是123456789，最后面的987654321;

從右向左掃描若都是增的，就到了987654321，也就沒(méi)有下一個(gè)了。否則找出第一次出現(xiàn)下降的位置。

如何得到346987521的下一個(gè)?

首先對(duì)原生字符串排序，這個(gè)迭代算法是基于字典序排序好的字符串全排列;(所以之后從尾部，向前循環(huán)迭代，每次變化盡可能短的后綴，以此類(lèi)推)

1.從尾部往前找第一個(gè)P(i-1) < P(i)的位置;： 346987521 種 最終找到6是第一個(gè)變小的數(shù)字，記錄下6的位置i-1

2.從找到的 i 位置往后找到最后一個(gè)大于6的數(shù)：346987521 中最終找到7的位置，記錄位置為m（m == r-1）

3.swap(r-1,i-1) : 3 4 7 9 8 6 5 2 1

4.倒序翻轉(zhuǎn)i位置后的所有數(shù)據(jù) : 3 4 7 1 2 5 6 8 9

5.進(jìn)行do-while循環(huán)，直到第一步之后，判斷出 i==0 break; 全部排列完畢

很抽象，但是思想就是 一個(gè)字符串的下一個(gè)全排列：有盡可能長(zhǎng)的共同前綴;變化限制在盡可能短的后綴上

大概知道步驟： 那么用排好序的123456789試試上面的過(guò)程，你會(huì)發(fā)現(xiàn)，每次變化盡可能短的后綴，有點(diǎn)像遞歸的感覺(jué)，一步一步逼近字符串0，index，此時(shí)完美結(jié)束; 或者用123這個(gè)例子體驗(yàn)一下6個(gè)全排列是咋來(lái)的 amazing

上面的過(guò)程多悟幾遍就理解了; 大概知道思想面試的時(shí)候說(shuō)說(shuō)也行=-=

實(shí)現(xiàn)代碼(有無(wú)重復(fù)不影響)

#include<iostream>
#include<algorithm>
#include<set>
using namespace std;

//dfs實(shí)現(xiàn)全排列



int main()
{
	string s = "abcd";
	
	sort(s.begin(),s.end());//記得先排序
	
	int len = s.size();
	do
	{
		cout << s << endl;//打印某次排列

		int i = s.size() - 1;
		int j;
		while (i > 0 && s[i] <= s[i - 1]) i--;//1.從后向前 找 第一個(gè) s[i-1]<s[i]

		if (i == 0) break;

		j = i;

		while (j<len && s[j]>s[i - 1]) j++;//2.從i向后 找 最后一個(gè) s[m]>s[i-1] 用j找，所以最后m==j-1

		swap(s[i - 1], s[j - 1]);//3. swap (i-1,m(j-1))

		reverse(s.begin() + i, s.end());  //4. 翻轉(zhuǎn) i后面的子串

		

	} while (1); //do while為了讓第一個(gè) abcd 也正常打印再全排列

	return 0;
}

這個(gè)算法理解起來(lái)對(duì)于我來(lái)說(shuō)有點(diǎn)夸張，嗚嗚嗚;

以上就是C++中字符串全排列算法及next_permutation原理詳解的詳細(xì)內(nèi)容，更多關(guān)于C++字符串全排列 next_permutation的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論