快捷導(dǎo)航

C語言實現(xiàn)的排列組合問題的通用算法、解決方法

更新時間：2014年08月28日 10:28:35 投稿：junjie

這篇文章主要介紹了C語言實現(xiàn)的排列組合問題的通用算法、解決方法,本文使用C語言實現(xiàn)在程序中解決這個問題,需要的朋友可以參考下

盡管排列組合是生活中經(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)：

復(fù)制代碼代碼如下:

/// 求從數(shù)組a[1..n]中任選m個元素的所有組合。

/// a[1..n]表示候選集，n為候選集大小，n>=m>0。

/// b[1..M]用來存儲當(dāng)前組合中的元素(這里存儲的是元素下標)，

/// 常量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)化為相應(yīng)的非遞歸程序，所以組合問題又可以用回溯的方法來解決。為了便于理解，我們可以把組合問題化歸為圖的路徑遍歷問題，在n個數(shù)中選取m個數(shù)的所有組合，相當(dāng)于在一個這樣的圖中（下面以從1,2,3,4中任選3個數(shù)為例說明）求從[1,1]位置出發(fā)到達[m,x](m<=x<=n)位置的所有路徑：

復(fù)制代碼代碼如下:

上圖是截取n×n右上對角矩陣的前m行構(gòu)成，如果把矩矩中的每個元素看作圖中的一個節(jié)點，我們要求的所有組合就相當(dāng)于從第一行的第一列元素[1,1]出發(fā)，到第三行的任意一列元素作為結(jié)束的所有路徑，規(guī)定只有相鄰行之間的節(jié)點，并且下一行的節(jié)點必須處于上一行節(jié)點右面才有路徑相連，其他情況都無路徑相通。顯然，任一路徑經(jīng)過的數(shù)字序列就對應(yīng)一個符合要求的組合。

下面是非遞歸的回溯方法的實現(xiàn)：

復(fù)制代碼代碼如下:

/// 求從數(shù)組a[1..n]中任選m個元素的所有組合。
/// 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]++;                // 在當(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;
}

下面是測試以上函數(shù)的程序：

復(fù)制代碼代碼如下:

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. 從當(dāng)前序列最尾端開始往前尋找兩個相鄰元素，令前面一個元素為*i，后一個元素為*ii，且滿足*i<*ii；

2. 再次從當(dāng)前序列末端開始向前掃描，找出第一個大于*i的元素，令為*j（j可能等于ii），將i，j元素對調(diào)；

3. 將ii之后（含ii）的所有元素顛倒次序，這樣所得的排列即為當(dāng)前序列的下一個排列。

其實現(xiàn)代碼如下：

復(fù)制代碼代碼如下:

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來求取某個序列全排列的方法：

復(fù)制代碼代碼如下:

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ù)值的從小到大的順序排列的，如果初始序列無序的話，上面程序只能求出從當(dāng)前序列開始的后續(xù)部分排列，也就是說next_permutation求出的排列是按排列從小到大的順序進行的。

您可能感興趣的文章: