C語言實現(xiàn)的排列組合問題的通用算法、解決方法
盡管排列組合是生活中經(jīng)常遇到的問題，可在程序設計時，不深入思考或者經(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步，直到當前可選編號最大的數(shù)為m。
很明顯，上述方法是一個遞歸的過程，也就是說用遞歸的方法可以很干凈利索地求得所有組合。
下面是遞歸方法的實現(xiàn)：
/// 求從數(shù)組a[1..n]中任選m個元素的所有組合。
/// a[1..n]表示候選集，n為候選集大小，n>=m>0。
/// b[1..M]用來存儲當前組合中的元素(這里存儲的是元素下標)，
/// 常量M表示滿足條件的一個組合中元素的個數(shù)，M=m，這兩個參數(shù)僅用來輸出結(jié)果。
void combine( int a[], int n, int m, int b[], const int M )
{
for(int i=n; i>=m; i--) // 注意這里的循環(huán)范圍
{
b[m-1] = i - 1;
if (m > 1)
combine(a,i-1,m-1,b,M);
else // m == 1, 輸出一個組合
{
for(int j=M-1; j>=0; j--)
cout << a[b[j]] << " ";
cout << endl;
}
}
}
因為遞歸程序均可以通過引入棧，用回溯轉(zhuǎn)化為相應的非遞歸程序，所以組合問題又可以用回溯的方法來解決。為了便于理解，我們可以把組合問題化歸為圖的路徑遍歷問題，在n個數(shù)中選取m個數(shù)的所有組合，相當于在一個這樣的圖中（下面以從1,2,3,4中任選3個數(shù)為例說明）求從[1,1]位置出發(fā)到達[m,x](m<=x<=n)位置的所有路徑：
1 2 3 4
2 3 4
3 4
上圖是截取n×n右上對角矩陣的前m行構(gòu)成，如果把矩矩中的每個元素看作圖中的一個節(jié)點，我們要求的所有組合就相當于從第一行的第一列元素[1,1]出發(fā)，到第三行的任意一列元素作為結(jié)束的所有路徑，規(guī)定只有相鄰行之間的節(jié)點，并且下一行的節(jié)點必須處于上一行節(jié)點右面才有路徑相連，其他情況都無路徑相通。顯然，任一路徑經(jīng)過的數(shù)字序列就對應一個符合要求的組合。
下面是非遞歸的回溯方法的實現(xiàn)：
/// a[1..n]表示候選集，m表示一個組合的元素個數(shù)。
/// 返回所有組合的總數(shù)。
int combine(int a[], int n, int m)
{
m = m > n ? n : m;
int* order = new int[m+1];
for(int i=0; i<=m; i++)
order[i] = i-1; // 注意這里order[0]=-1用來作為循環(huán)判斷標識
int count = 0;
int k = m;
bool flag = true; // 標志找到一個有效組合
while(order[0] == -1)
{
if(flag) // 輸出符合要求的組合
{
for(i=1; i<=m; i++)
cout << a[order[i]] << " ";
cout << endl;
count++;
flag = false;
}
order[k]++; // 在當前位置選擇新的數(shù)字
if(order[k] == n) // 當前位置已無數(shù)字可選，回溯
{
order[k--] = 0;
continue;
}
if(k < m) // 更新當前位置的下一位置的數(shù)字
{
order[++k] = order[k-1];
continue;
}
if(k == m)
flag = true;
}
delete[] order;
return count;
}
下面是測試以上函數(shù)的程序：
int main()
{
const int N = 4;
const int M = 3;
int a[N];
for(int i=0;i<N;i++)
a[i] = i+1;
// 回溯方法
cout << combine(a,N,3) << endl;
// 遞歸方法
int b[M];
combine(a,N,M,b,M);
return 0;
}
由上述分析可知，解決組合問題的通用算法不外乎遞歸和回溯兩種。在針對具體問題的時候，因為遞歸程序在遞歸層數(shù)上的限制，對于大型組合問題而言，遞歸不是一個好的選擇，這種情況下只能采取回溯的方法來解決。
n個數(shù)的全排列問題相對簡單，可以通過交換位置按序枚舉來實現(xiàn)。STL提供了求某個序列下一個排列的算法next_permutation，其算法原理如下：
1. 從當前序列最尾端開始往前尋找兩個相鄰元素，令前面一個元素為*i，后一個元素為*ii，且滿足*i<*ii；
2. 再次從當前序列末端開始向前掃描，找出第一個大于*i的元素，令為*j（j可能等于ii），將i，j元素對調(diào)；
3. 將ii之后（含ii）的所有元素顛倒次序，這樣所得的排列即為當前序列的下一個排列。
其實現(xiàn)代碼如下：
template <class BidirectionalIterator>
bool next_permutation(BidirectionalIterator first, BidirectionalIterator last)
{
if (first == last) return false; // 空範圍
BidirectionalIterator i = first;
++i;
if (i == last) return false; // 只有一個元素
i = last; // i 指向尾端
--i;
for(;;)
{
BidirectionalIterator ii = i;
--i;
// 以上，鎖定一組（兩個）相鄰元素
if (*i < *ii) // 如果前一個元素小於後一個元素
{
BidirectionalIterator 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;
}
}
}
下面程序演示了利用next_permutation來求取某個序列全排列的方法：
int main()
{
int ia[] = {1,2,3,4};
vector<int> iv(ia,ia+sizeof(ia)/sizeof(int));
copy(iv.begin(),iv.end(),ostream_iterator<int>(cout," "));
cout << endl;
while(next_permutation(iv.begin(),iv.end()))
{
copy(iv.begin(),iv.end(),ostream_iterator<int>(cout," "));
cout << endl;
}
return 0;
}
注意：上面程序中初始序列是按數(shù)值的從小到大的順序排列的，如果初始序列無序的話，上面程序只能求出從當前序列開始的后續(xù)部分排列，也就是說next_permutation求出的排列是按排列從小到大的順序進行的。
相關(guān)文章
C++基于reactor的服務器百萬并發(fā)實現(xiàn)與講解
這篇文章主要介紹了C++基于reactor的服務器百萬并發(fā)實現(xiàn)與講解，本文通過實例圖文相結(jié)合給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下2022-07-07
這篇文章主要介紹了EasyC++靜態(tài)持續(xù)變量，除了自動存儲變量之后，C++當中還有靜態(tài)持續(xù)變量。關(guān)于靜態(tài)持續(xù)變量的定義C++和C語言是一樣的，它擁有三種鏈接性，即外部鏈接性、內(nèi)部連接性和無鏈接性，下面一起進入文章了解更具體內(nèi)容吧2021-12-12
這篇文章主要為大家詳細介紹了C語言實現(xiàn)會員管理系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-03-03
這篇文章主要介紹了qt實現(xiàn)倒計時示例,需要的朋友可以參考下2014-05-05
本篇文章對指針與const限定符的使用進行了分析介紹。需要的朋友參考下2013-05-05
這篇文章主要為大家詳細介紹了C語言實現(xiàn)車輛信息管理系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-03-03
C 二分查找 遞歸與非遞歸的實現(xiàn)代碼，需要的朋友可以參考一下2013-03-03
分享一下8年C++面向?qū)ο笤O計的經(jīng)驗體會
關(guān)于C++程序設計的書藉非常多，本章不講C++的語法，只講一些小小的編程道理。如果我能早幾年明白這些小道理，就可以大大改善數(shù)十萬行程序的質(zhì)量了2017-07-07
求子數(shù)組最大和的實例代碼，需要的朋友可以參考一下2013-03-03
C++面向?qū)ο笳Z言自制多級菜單功能實現(xiàn)代碼
菜單類主要負責菜單的創(chuàng)建、修改、刪除,是包含菜單結(jié)構(gòu)組織和響應函數(shù)的模型,用戶擁有充分的自主性,可根據(jù)需要自定義菜單顯示和響應函數(shù),這篇文章主要介紹了C++面向?qū)ο笳Z言自制多級菜單,需要的朋友可以參考下2024-06-06