全排列參考了兩位的部落格 感謝!
http://blog.sina.com.cn/s/blog_9f7ea4390101101u.html
http://blog.csdn.net/ac_gibson/article/details/45308645
早就聽說了了next_permutation 産生全排列的強大,一直到昨晚遇到一個對字元串産生全排列的問題才知道這個函數的強大,我們隊是按照dfs去搞全排列,然後在進行字元串的比對,結果寫的很長,過程中還各種debug。。。于是決定今天學一下...
next_permutation函數
組合數學中經常用到排列，這裡介紹一個計算序列全排列的函數：next_permutation（start,end），和prev_permutation（start,end）。這兩個函數作用是一樣的，差別就在于前者求的是目前排列的下一個排列，後一個求的是目前排列的上一個排列。至于這裡的“前一個”和“後一個”，我們可以把它了解為序列的字典序的前後，嚴格來講，就是對于目前序列pn，他的下一個序列pn+1滿足：不存在另外的序列pm，使pn<pm<pn+1.
對于next_permutation函數，其函數原型為：
#include <algorithm>
bool next_permutation(iterator start,iterator end)
當目前序列不存在下一個排列時，函數傳回false，否則傳回true
我們來看下面這個例子：
[cpp] view plain copy
- #include <iostream>
- #include <algorithm>
- using namespace std;
- int main()
- {
- int num[3]={1,2,3};
- do
- {
- cout<<num[0]<<" "<<num[1]<<" "<<num[2]<<endl;
- }while(next_permutation(num,num+3));
- return 0;
- }
輸出結果為：
當我們把while(next_permutation(num,num+3))中的3改為2時，輸出就變為了：
由此可以看出，next_permutation(num,num+n)函數是對數組num中的前n個元素進行全排列，同時并改變num數組的值。
另外，需要強調的是，next_permutation（）在使用前需要對欲排列數組按升序排序，否則隻能找出該序列之後的全排列數。比如，如果數組num初始化為2,3,1，那麼輸出就變為了：
此外，next_permutation（node,node+n,cmp）可以對結構體num按照自定義的排序方式cmp進行排序。
也可以對字元...
next_permutation 自定義比較函數 POJ 1256
題目中要求的字典序是
//'A'<'a'<'B'<'b'<...<'Z'<'z'.
。。。
#include<iostream> //poj 1256 Anagram
#include<string>
#include<algorithm>
using namespace std;
int cmp(char a,char b)
{
if(tolower(a)!=tolower(b))//tolower 是将大寫字母轉化為小寫字母.
return tolower(a)<tolower(b);
else
return a<b;
}
int main()
{
char ch[20];
int n;
cin>>n;
while(n--)
{
scanf("%s",ch);
sort(ch,ch+strlen(ch),cmp);
do
{
printf("%s\n",ch);
}while(next_permutation(ch,ch+strlen(ch),cmp));
}
return 0;
}
練習
部落客個人公衆号開通啦，平時主要分享一些機器學習、深度學習等的論文和方法，以及算法與資料結構、大廠經驗貼等！歡迎大家關注，一起交流進步！