列舉
對于一些簡單的題目，我們或許不需要用什么太巧妙的方法，只需要把所有的可能性列舉出來，然后逐一試驗就可以了，
方法
通過事先把各種可能發生的事情都列舉一遍，為后面求解提供結果，
常見型別
列舉排列
列舉子集
遞回
基本思想
通過不斷呼叫自己，把一個復雜問題層層轉化為規模更小的相似問題，
補充
next permutation/prev permutation(全排列演算法)
STL提供了兩個用來計算排列組合關系的演算法，分別是next permutation（“下一個”排列組合）和prev permutation（“前一個”排列組合），首先我們需要了解什么是“下一個”排列組合，什么是“前一個”排列組合，
考慮三個字符所組成的序列{a,b,c}，這個序列有六個可能的排列組合：abc，acb，bac，bca，cab，cba，這些排列組合根據less-than運算子做字典順序(lexicographical)的排序，也就是說，abc是第一個排列組合，因為每一個元素都小于其后的元素，acb是次一個排列組合，因為它是固定了a(序列內最小元素)之后所做的新組合，
同樣道理，那些固定b(序列中次小元素)而做的排列組合，在次序上將先于那些固定c而做的排列組合，以bac和bca為例，bac在bca之前，因為次序ac小于序列ca，面對bca，我們可以說其前一個排列組合是bac，而其后一個排列組合是cab，序列abc沒有“前一個”排列組合，cba沒有“后一個”排列組合，
next permutation()會取得[first,last)所標示的序列的下一個排列組合，如果沒有下一個排列組合，便回傳false；否則回傳true，這個演算法有兩個版本，版本一使用元素型別所提供的less-than運算子來決定下一個排列組合，版本二則是以仿函式comp來決定，
演算法思想
首先從最尾端開始往前尋找兩個相鄰元素，令第一元素為i,第二元素為ii,且滿足i<ii，
找到這樣一組相鄰元素后，再從最尾端開始往前檢驗，找出第一個大于i的元素，令其為j，將i,j元素對調(swap)，
再將ii之后的所有元素顛倒(reverse)排序，
舉個例子，假設有序列{0,1,2,3,4}，下圖便是套用上述演演算法則，一步一步獲得“下一個”排列組合，圖中只框出那符合“一元素為i,第二元素為ii,且滿足i<ii ”的相鄰兩元素，至于尋找適當的j、對調、逆轉等操作未顯示出，
以下是版本一的實作，版本二類似，就不列出來了，
template<calss BidrectionalIterator>
bool next_permutation(BidrectionalIterator first,BidrectionalIterator last)
{
if(first == lase) return false; /* 空區間 */
BidrectionalIterator i = first;
++i;
if(i == last) return false; /* 只有一個元素 */
i = last; /* i指向尾端 */
--i;
for(;;)
{
BidrectionalIterator ii = i;
--i;
/* 以上鎖定一組(兩個)相鄰元素 */
if(*i < *ii) /* 如果前一個元素小于后一個元素 */
{
BidrectionalIterator j = last; /* 令j指向尾端 */
while(!(*i < *--j)); /* 由尾端往前找，直到遇到比*i大的元素 */
iter_swap(i,j); /* 交換i,j */
reverse(ii,last); /* 將ii之后的元素全部逆序重排 */
return true;
}
if(i == first) /* 進行至最前面了 */
{
reverse(first,last); /* 全部逆序重排 */
return false;
}
}
}應用
輸出序列{1,2,3,4}字典序的全排列，
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int ans[4]={1,2,3,4};
sort(ans,ans+4); /* 這個sort可以不用，因為{1，2，3，4}已經排好序*/
do /*注意這步，如果是while回圈，則需要提前輸出*/
{
for(int i=0;i<4;++i)
cout<<ans[i]<<" ";
cout<<endl;
}while(next_permutation(ans,ans+4));
return 0;
}算出集合{1, 2, ..., m}的第n個排列
樣例：
7個數的集合為{1, 2, 3, 4, 5, 6, 7}，要求出第n=1654個排列，
(1654 / 6!)取整得2，確定第1位為3（從0開始計數），剩下的6個數{1, 2, 4, 5, 6, 7}，求第1654 % 6!=214個序列；
(214 / 5!)取整得1，確定第2位為2，剩下5個數{1, 4, 5, 6, 7}，求第214 % 5!=94個序列；
(94 / 4!)取整得3，確定第3位為6，剩下4個數{1, 4, 5, 7}，求第94 % 4!=22個序列；
(22 / 3!)取整得3，確定第4位為7，剩下3個數{1, 4, 5}，求第22 % 3!=4個序列；
(4 / 2!)得2，確定第5為5，剩下2個數{1, 4}；由于4 % 2!=0，故第6位和第7位為增序<1 4>；
因此所有排列為：3267514，
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int ans[7]={1,2,3,4,5,6,7};
sort(ans,ans+7); /* 同上可以不用sort */
int n=0;
do //注意這步，如果是while回圈，則需要提前輸出
{
if(n == 1654)
{
for(int i=0;i<7;++i)
cout<<ans[i];
cout<<endl;
break;
}
n++;
}while(next_permutation(ans,ans+7));
return 0;
}
給定一個排列，算出這是第幾個排列
和上一個問題的推導程序相反，
如3267514：
后6位的全排列為6！，3為{1, 2, 3 ,4 , 5, 6, 7}中第2個元素（從0開始計數），故2*720=1440；
后5位的全排列為5！，2為{1, 2, 4, 5, 6, 7}中第1個元素，故1*5!=120；
后4位的全排列為4！，6為{1, 4, 5, 6, 7}中第3個元素，故3*4!=72；
后3位的全排列為3！，7為{1, 4, 5, 7}中第3個元素，故3*3!=18；
后2位的全排列為2！，5為{1, 4, 5}中第2個元素，故2*2!=4；
最后2位為增序，因此計數0，求和得：1440+120+72+18+4=1654
這個的代碼實作，可以用一個陣列a保存3267514,然后while呼叫next_permutation(),用n計數，每次與陣列a比較，相等則輸出n;
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/448056.html
標籤：C++