https://www.nowcoder.com/acm/contest/76/H

給一道題，可以去測試代碼。

這里總結一下全排列的幾種方法：

方法一：利用交換排列：缺點：不能按字典序排列，但可以借助set處理。

#include <bits/stdc++.h> //不會按字典序排列 using namespace std;void pre(string str, int s, int e){if(s == e){cout << str << endl;}else{for(int i = s; i <= e; i++){if(i != s && str[i] == str[s]) //去重，除了第一位，其余的相同時無須交換 continue;swap(str[i], str[s]);pre(str, s + 1, e);swap(str[i], str[s]);}} }int main(){string str;cin >> str;pre(str, 0, str.length() - 1);return 0; }

　　方法二：利用dfs，只能處理沒有重復元素的字符串

#include <bits/stdc++.h> using namespace std; char str[100]; char mu[100];void dfs(int len, int n){if(len == n){cout << mu << endl;return ;}for(int i = 0; i < n; i++){ //嘗試放入每個字符 int flag = 1;for(int j = 0; j < len; j++){ //檢測這個字符是否已經放入過 if(mu[j] == str[i]){flag = 0;break;}}if(flag){mu[len] = str[i];dfs(len + 1, n); }} }int main(){cin >> str;sort(str, str + strlen(str)); dfs(0, strlen(str));return 0; }

　　方法三：dfs: 感覺這個是比較理想的，可以按字典序排好輸出，并能去重，一定要掌握！！！

對于A1,B,A2進行排序,(這里的A1, A2代表相同元素，下標是為了區分)
首先sort一下變成：A1，A2，B
然后第一趟：
A1，A2，B
A1, B, A2
然后遍歷到A2開頭了，好，后面查找下一個時，從i=0開始，
于是判斷A1是否訪問過，未訪問則進行最關鍵的步驟了：
檢測A1之后是否有已訪問的且和A1相等，如若是則放棄A1繼續遍歷。
這里有點不好理解，對于A1A2B的序列，可知A1再前所以以A開頭的
必定是以A1開頭，所以在嘗試A2開始頭時，遍歷嘗試放入第二個元
素時判斷A1雖然當前未訪問過，但他是在A2之前，一定在之前的全
排列之中了，故放棄。
感覺還是不太好理解；還是自己在紙上畫畫，模擬一下，多體會體會。

?

#include <bits/stdc++.h> using namespace std; const int N = 1e3; char str[N]; char buf[N]; int toal, len; bool visit[N];void pre(int num){if(num == len){cout << buf << endl;toal++;return ;}for(int i = 0; i < len; i++){if(!visit[i]){bool flag = 1;for(int j = i + 1; j < len; j++){if(visit[j] && str[j] == str[i]){ //檢測重復 flag = 0;break;}}if(flag){buf[num] = str[i]; //這里不能寫成：buf[num++] = str[i];因為for循環沒有結束還要用num,不能改變num的值 visit[i] = 1;pre(num + 1); visit[i] = 0;}}} }int main(){cin >> str;len = strlen(str);sort(str, str + len);pre(0);cout << "toal: " << toal << endl;return 0; }

?

　　

?

轉載于:https://www.cnblogs.com/zhumengdexiaobai/p/8530605.html

總結

以上是生活随笔為你收集整理的5-全排列总结：的全部內容，希望文章能夠幫你解決所遇到的問題。

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