C++範例分析組合數的計算與排列組合的產生

2022-07-19 18:02:22

組合數的計算

使用加法遞推—O(n^2)

邊界條件

int C[1001][1001]; // 根據實際需要開陣列，必要時採用高精度型別
//……
memset(C,0,sizeof(C));
for (int i=0;i<=n;i++)
{
C[i][0]=1;
for (int j=0;j<=i;j++)
C[i][j]=C[i-1][j-1] + C[i-1][j];
}

使用乘法遞推—O(n)

邊界條件

必須先乘後除，否則除不開

一個小優化：

（m＞n/2時用）

int C[1001]; // C[m]其實表示C[n][m]，必要時採用高精度型別
……
C[0]=1;
if (m>n-m) m=n-m;
for (int i=1;i<=m;i++)
C[i] = (n-i+1) * C[i-1] / i; // 如果怕溢位，可以把中間結果轉化成long long。

排列和組合的產生(無重集元素)

int item[N]; // 第i位要放置的數位
bool used[N];
int n,m;

全排列

將 n 個數位 1～n 進行排序，有多少種排序方法？

使用深度優先搜尋，對 n 個位置逐個進行試探。時間複雜度為 O(n!)。

void full_ permutation(int depth)
{
if (depth==n)
{
// print(); // 輸出結果
return;
}
for (int i=0; i<n; i++)
if (!used[i])
{
used[i]=true;
item[depth]=i+1;
try(depth+1);
used[i]=false; // 別忘記清除」使用」標記
}
}

一般組合

從 n 個元素 1～n 中任取 m 個元素，有多少種取法？

一個合法的組合有這樣一個特點：排在右面的數位一定嚴格大於左面的數位。比如說某一位上取了 3，那麼從 4 開始搜尋下一位就可以了。

void combination(int depth, int p)
{
if (depth==m)
{
// print(); // 輸出結果
return;
}
for (int i=p+1 ; i<n-(m-depth) ; i++)
{
// 由於後面的元素一定前面的大，所以不需要標記used了。
item[depth]=i;
try(depth+1);
}
}
combination(0,0);

全組合

輸入 n 個數，求這 n 個數構成的集合的所有非空子集。

和一般組合不同，這次只要產生一個解，就馬上輸出。

void full_combination(int l, int p)
{ 
for (int i=0; i<l; i++) // 每次進入遞迴函數都輸出
cout<<item[i]<<" "; 
cout<<endl; 
for (int i=p; i<n; i++)
{ 
item[l] = i; // 在l位置放上該數
full_combination(l+1, i+1); // 填下一個位置
} 
}
full_combination(0, 0);

注意：對於一個整數，每一位不是 0 就是 1，所以可以用整數來表示一個集合。具體範例可參見 “2.8Healthy Holsteins”。

由上一排列產生下一排列

① 從右往左尋找第一個小於右邊的數，位置為 j。

② 在 j 位置的右邊尋找大於 aj的最小數位 ak（位置 k）

③ 將 aj 與 ak的值進行交換

④ 將數列的 j+1 位到 n 位倒轉。

int a[N]; // 初始化：a[i]是字典序最小的排列, 0≤i＜N
int j,k, p,q, temp;
j=(n-1) - 1;
while ((j>=0)&&(a[j]>a[j+1])) j--; // 從右往左尋找第一個小於右邊的數，位置為j。
if (j>=0) // 如果j<0說明已經排完了。
{
k=n-1;
while (a[k]<a[j]) k--; // 在j位置的右邊尋找大於aj的最小數位ak（位置k）
swap(a[j], a[k]); // 將aj與ak的值進行交換
for (p=j+1,q=n-1; p<q; p++,q--) // 將數列的j+1位到n位倒轉
swap(a[p], a[q]);
}

STL 中有與此相同的演演算法。標頭檔案為<algorithm>。

next_permutation(序列第一項的地址, 序列最後一項的地址+1)：產生下一排列。

prev_permutation(序列第一項的地址, 序列最後一項的地址+1)：產生上一排列。

這兩個函數能夠用於可重集的排列。

由上一組合產生下一組合

① 從右向左尋找可以往下取一個元素的數，位置為 j。

（舉個例子：從 7 個數中取 4 個數，有一個組合為 1367，那麼 6、7 就不能再往下取了）

② 數列的 j 位到 n 位重新取元素。

注意：

① 從 N 個連續元素中取 M 個元素。如果元素序號不連續，就需要修改下面的“+1”。

② 右側的數位一定嚴格大於左側的數位。

int a[M]; // 初始化：a[i]是字典序最小的排序, 0≤i＜M，1≤a[i]≤N
//……
int j=m-1;
while ((j>=0)&&(a[j]==n-(m-1 -j))) j--;
if (i>=0)
{
a[j]++;
for (int k=j+1; k<m; k++) a[k]=a[k-1]+1;
}

到此這篇關於C++範例分析組合數的計算與排列組合的產生的文章就介紹到這了,更多相關C++組合數的計算內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！