前幾天在論壇看到一個文章，計算組合數，有點數學基礎的都知道，求組合用公式Cnr（= n!/(n-r)!r!）可以得到組合數。怎樣通過程式實作得到每一個組合序列呢？以整型資料為例：
Ex:
N = {1,2,3,4,5}
從N中5個元素取2個得到
12 13 14 15 23 24 25 34 35 45 ——10個組合
這裡可以看到組合出現是有規律的，每個組合總是按N中元素順序出現（組合不是排列，12和21屬于同一組合），其次，相鄰組合後者在前者基礎上從最末元素開始按N中元素順序遞增。
這是個很有用的資訊，如果我們要輸出每個組合序列，我們可以很自然的聯想到最直覺的解決辦法——遞歸回溯。論壇上那位朋友也是用的這個思想設計解法。
現給出代碼,在長度為N順序整型資料中選取長度為R的組合序列：
// 參數說明：a記錄組合序列，k1為組合坐标，k2為輔助參數
void combination( int a[], int n, int r, int k1, int k2)... ... {
if (k1 == r)......{ //輸出目前序列
for (int i = 0;i < r;++i)
cout << a[i] << " ";
cout << endl;
}
else
for (int i = k2;i < n;++i)......{
a[k1] = i+1; //子序列指派
combination(a,n,r,k1+1,i+1); //遞歸回溯
}
}
代碼很簡單。這個問題現在可以算解決了吧？不然，由此我想到，如果目前集合N并非順序排列，如果要想對每次得到的R序列做特定處理。那麼僅僅這樣是不夠的。為了增加實用性，如果把它設計成一個泛型算法，是否效果更好。
有了初步設想，進一步考慮，N序列應該由使用者定義，用容器R來儲存組合序列，并由使用者設定對目前R中組合序列的操作。
下面是模闆函數：
// 參數說明：begin,end分别為雙向疊代器，col為坐标，初始為0，loop循環次數，由N,R長度差決定，func 使用者定義函數
template < class BidIt, class Func >
void combination_recursive(BidIt n_begin,BidIt n_end, int n_col,
BidIt r_begin,BidIt r_end, int r_col, int loop,Func func) ... {
int r_size = r_end-r_begin; //擷取R長度
int curr_n_col = n_col;
int curr_loop = loop;
if (r_col == r_size) //産生組合序列
func(r_begin,r_end);
else
for (int i = 0;i <= loop;++i)...{
BidIt r_it = r_begin; //擷取R疊代器位置
for (int r_cnt = 0;r_cnt < r_col;++r_cnt)
++r_it;
BidIt n_it = n_begin; //擷取N疊代器位置
for (int n_cnt = 0;n_cnt < n_col+i;++n_cnt)
++n_it;
*r_it = *n_it; //指派
++curr_n_col;
//遞歸回溯
combination_recursive(n_begin,n_end,curr_n_col,
r_begin,r_end,r_col+1,curr_loop,func);
--curr_loop;
}
}
函數用法：
Ex:
到這裡，最初的設想得以實作。但是又存在一個問題，算法combination用到了遞歸，在大規模的輸入時，入棧的深度會消耗大量的記憶體空間，其次，盡管我們自定義的函數可以實作需要的操作，但是用途是很有限的，并且不能靈活的篩選需要的組合序列。
與“組合”相關的字眼就是“排列”了，在STL算法庫中，next_permutation是個很好的範例（參見blog中另一文章《stl算法：next_permutation剖析》），能否設計一個類似這樣的範型算法解決我們的問題？答案是肯定的。因為在最初的例子中得出組合的兩個性質，說明組合間是有序的，由一個組合序列是可以得出下一個組合序列的。
下面是combination的函數原型：
template < class BidIt >
bool next_combination(BidIt n_begin,BidIt n_end,
BidIt r_begin,BidIt r_end);
template < class BidIt, class Pred >
bool next_combination(BidIt n_begin,BidIt n_end,
BidIt r_begin,BidIt r_end
Pred equal);
template < class BidIt >
bool prev_combination(BidIt n_begin,BidIt n_end,
BidIt r_begin,BidIt r_end);
template < class BidIt, class Pred >
bool prev_combination(BidIt n_begin,BidIt n_end,
BidIt r_begin,BidIt r_end,
Pred equal);
算法線上性時間内完成，并且采用疊，由于算法具體實作很繁雜，這裡隻做簡要說明。next_combination & prev_combination均采用從末端向前索引，根據比較N，R目前元素設定标記并産生下一組合序列。
函數用法：
Ex:
#include < iostream >
#include " combination.h "
using namespace std;
int main() ... {
char n[] = "abcdefg";
char r[] = "abc";
int count = 0;
do...{
cout << r << endl;
++count;
}
while (next_combination(n,n+7,r,r+3));
cout << count << endl;
cout << "finished" << endl;
system("pause");
}
若采用prev_combination，則需替換r為最大組合序列char r[] = “efg”。
注：本文算法雖全由我書寫完成但并非全由我設計，借鑒于網絡和書籍，歡迎讨論。