盡管排列組合是生活中經(jīng)常遇到的問題，可在程序設(shè)計時，不深入思考或者經(jīng)驗不足都讓人無從下手。由于排列組合問題總是先取組合再排列，并且單純的排列問題相對簡單，所以本文僅對組合問題的實現(xiàn)進行詳細討論。以在n個數(shù)中選取m(0<m<=n)個數(shù)為例，問題可分解為：
1. 首先從n個數(shù)中選取編號最大的數(shù)，然后在剩下的n-1個數(shù)里面選取m-1個數(shù)，直到從n-(m-1)個數(shù)中選取1個數(shù)為止。
2. 從n個數(shù)中選取編號次小的一個數(shù)，繼續(xù)執(zhí)行1步，直到當(dāng)前可選編號最大的數(shù)為m。
很明顯，上述方法是一個遞歸的過程，也就是說用遞歸的方法可以很干凈利索地求得所有組合。
下面是遞歸方法的實現(xiàn)：
下面是非遞歸的回溯方法的實現(xiàn)：
int* order = new int[m+1];
for(int i=0; i<=m; i++)
order[i] = i-1; // 注意這里order[0]=-1用來作為循環(huán)判斷標(biāo)識
int count = 0;
int k = m;
bool flag = true; // 標(biāo)志找到一個有效組合
while(order[0] == -1)
{
if(flag) // 輸出符合要求的組合
{
for(i=1; i<=m; i++)
cout << a[order[i]] << " ";
cout << endl;
count++;
flag = false;
}
order[k]++; // 在當(dāng)前位置選擇新的數(shù)字
if(order[k] == n) // 當(dāng)前位置已無數(shù)字可選，回溯
{
order[k--] = 0;
continue;
}
if(k < m) // 更新當(dāng)前位置的下一位置的數(shù)字
{
order[++k] = order[k-1];
continue;
}
if(k == m)
flag = true;
}
delete[] order;
return count;
}
// 回溯方法
cout << combine(a,N,3) << endl;
// 遞歸方法
int b[M];
combine(a,N,M,b,M);
return 0;
}
n個數(shù)的全排列問題相對簡單，可以通過交換位置按序枚舉來實現(xiàn)。STL提供了求某個序列下一個排列的算法next_permutation，其算法原理如下：
1. 從當(dāng)前序列最尾端開始往前尋找兩個相鄰元素，令前面一個元素為*i，后一個元素為*ii，且滿足*i<*ii；
2. 再次從當(dāng)前序列末端開始向前掃描，找出第一個大于*i的元素，令為*j（j可能等于ii），將i，j元素對調(diào)；
3. 將ii之后（含ii）的所有元素顛倒次序，這樣所得的排列即為當(dāng)前序列的下一個排列。
其實現(xiàn)代碼如下：