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ù)僅用來輸出結果。
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;
}
}
}
因為遞歸程序均可以通過引入棧,用回溯轉化為相應的非遞歸程序,所以組合問題又可以用回溯的方法來解決。為了便于理解,我們可以把組合問題化歸為圖的路徑遍歷問題,在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行構成,如果把矩矩中的每個元素看作圖中的一個節(jié)點,我們要求的所有組合就相當于從第一行的第一列元素[1,1]出發(fā),到第三行的任意一列元素作為結束的所有路徑,規(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求出的排列是按排列從小到大的順序進行的。
上一篇:C++指針數(shù)組、數(shù)組指針、數(shù)組名及二維數(shù)組技巧匯總
欄 目:C語言
本文標題:C語言實現(xiàn)的排列組合問題的通用算法、解決方法
本文地址:http://mengdiqiu.com.cn/a1/Cyuyan/3450.html
您可能感興趣的文章
- 04-02c語言函數(shù)調(diào)用后清空內(nèi)存 c語言調(diào)用函數(shù)刪除字符
- 04-02c語言的正則匹配函數(shù) c語言正則表達式函數(shù)庫
- 04-02func函數(shù)+在C語言 func函數(shù)在c語言中
- 04-02c語言中對數(shù)函數(shù)的表達式 c語言中對數(shù)怎么表達
- 04-02c語言用函數(shù)寫分段 用c語言表示分段函數(shù)
- 04-02c語言編寫函數(shù)冒泡排序 c語言冒泡排序法函數(shù)
- 04-02c語言沒有round函數(shù) round c語言
- 04-02c語言分段函數(shù)怎么求 用c語言求分段函數(shù)
- 04-02C語言中怎么打出三角函數(shù) c語言中怎么打出三角函數(shù)的值
- 04-02c語言調(diào)用函數(shù)求fibo C語言調(diào)用函數(shù)求階乘


閱讀排行
本欄相關
- 04-02c語言函數(shù)調(diào)用后清空內(nèi)存 c語言調(diào)用
- 04-02func函數(shù)+在C語言 func函數(shù)在c語言中
- 04-02c語言的正則匹配函數(shù) c語言正則表達
- 04-02c語言用函數(shù)寫分段 用c語言表示分段
- 04-02c語言中對數(shù)函數(shù)的表達式 c語言中對
- 04-02c語言編寫函數(shù)冒泡排序 c語言冒泡排
- 04-02c語言沒有round函數(shù) round c語言
- 04-02c語言分段函數(shù)怎么求 用c語言求分段
- 04-02C語言中怎么打出三角函數(shù) c語言中怎
- 04-02c語言調(diào)用函數(shù)求fibo C語言調(diào)用函數(shù)求
隨機閱讀
- 08-05dedecms(織夢)副欄目數(shù)量限制代碼修改
- 01-11ajax實現(xiàn)頁面的局部加載
- 08-05織夢dedecms什么時候用欄目交叉功能?
- 04-02jquery與jsp,用jquery
- 08-05DEDE織夢data目錄下的sessions文件夾有什
- 01-10C#中split用法實例總結
- 01-10delphi制作wav文件的方法
- 01-10SublimeText編譯C開發(fā)環(huán)境設置
- 01-10使用C語言求解撲克牌的順子及n個骰子
- 01-11Mac OSX 打開原生自帶讀寫NTFS功能(圖文