組合
此條目需要擴充。 (2009年10月20日) |
在組合數學,一個集的元素的組合(英語:Combination)是一個子集。S的一個k-組合是S的一個有k個元素的子集。若兩個子集的元素完全相同並順序相異,它仍視為同一個組合,這是組合和排列不同之處。
表示方式
從 n 個不同元素中取出 k 個元素的所有不同組合的個數,叫做從 n 個不同元素中取出 k 個元素的組合數,記做:、、、(英語)、(法語、羅馬尼亞語、俄語、漢語(中國)[1]、波蘭語)。
理論與公式
從個元素中取出個元素,個元素的組合數量為:
以六合彩為例。在六合彩中從49顆球中取出6顆球的組合數量為:
在集合中取出k項元素
重複組合理論與公式
從個元素中取出個元素,個元素可以重複出現,這組合數量為:
以取色球為例,每種顏色的球有無限多顆,從8種色球中取出5顆球,好比是在5顆球間畫上分隔號「|」代表球色的分佈情形。例如第1種色球取1顆,第2種色球取2顆,第3種色球取2顆可以表示成:
- 球|球球|球球| | | | |
可以理解為8類球每類取多少個,一起構成5個球。我們把5個球排成一排,用7個分隔線去隔開。如上圖,表示含義:第1根線前表示第一類球取的個數,第1根和第2根線表示第二類球取的個數...第6第7根線前表示第七類球的個數,第7根後表示第八類球的個數。亦即問題是從(5+8-1)個位置中挑選出(8-1)個位置擺分隔號,這組合數量為:
因為組合數量公式特性,重複組合轉換成組合有另一種公式為:
另外也可以記為[2]或
取值範圍的擴充[3]
在的定義中,由於它有意義的範圍必須是滿足條件,所以其他範圍必須另外定義,我們有:
演算範例
組合 C
迴圈法
/***********************/
/** This is C++ code. **/
/** Comb Example **/
/***********************/
#include <iostream>
using namespace std;
bool next_comb(int* comb, const int n, const int k) {
int i = k - 1;
const int e = n - k;
do
comb[i]++;
while (comb[i] > e + i && i--);
if (comb[0] > e)
return 0;
while (++i < k)
comb[i] = comb[i - 1] + 1;
return 1;
}
int main() {
int n, k;
cout << "comb(n,k):" << endl;
cin >> n >> k;
if (n < k || k <= 0)
return 0;
int* comb = new int[k];
for (int i = 0; i < k; i++)
comb[i] = i;
do
for (int i = 0; i < k; cout << ((++i < k) ? ',' : '\n'))
cout << comb[i] + 1;
while (next_comb(comb, n, k));
delete[] comb;
return 0;
}
遞迴法
#include <iostream>
#include <cstdio>
using namespace std;
namespace comb {
int n, k;
int arr[12];
int count;
bool arrsame(int site) {
if (site > 0 && arr[site - 1] >= arr[site])
return 0;
return 1;
}
inline void arrprint() {
for (int i = 0; i < k; i++)
printf("%3d", arr[i]);
puts("");
count++;
}
void calculate(int now) {
if (now == k) {
arrprint();
return;
}
for (int i = 0; i < n; i++) {
arr[now] = i;
if (arrsame(now)) {
calculate(now + 1);
}
}
}
inline void run(int nn, int kk) {
n = nn, k = kk;
count = 0;
if (k < 12 && n >= k && k > 0)
calculate(0);
if (count)
printf("\n%d combination.\n\n", count);
else
puts("Input error!");
}
}
int main() {
int n, k;
while (scanf("%d%d", &n, &k) != EOF) {
comb::run(n, k);
fflush(stdout);
}
return 0;
}
重複組合 H
迴圈法
/***********************/
/** This is C++ code. **/
/** ReComb Example **/
/***********************/
#include <iostream>
using namespace std;
bool next_re_comb(int* recomb, const int n, const int k) {
int i = k - 1;
do
recomb[i]++;
while (recomb[i] > n - 1 && i--);
if (recomb[0] > n - 1)
return 0;
while (++i < k)
recomb[i] = recomb[i - 1];
return 1;
}
int main() {
int n, k;
cout << "recomb(n,k):" << endl;
cin >> n >> k;
if (n <= 0 || k <= 0)
return 0;
int* recomb = new int[k];
for (int i = 0; i < k; i++)
recomb[i] = 0;
do
for (int i = 0; i < k; cout << ((++i < k) ? ',' : '\n'))
cout << recomb[i] + 1;
while (next_re_comb(recomb, n, k));
delete[] recomb;
return 0;
}
遞迴法
#include <iostream>
#include <cstdio>
using namespace std;
namespace re_comb {
int n, k;
int arr[12];
int count;
bool arrsame(int site) {
if (site > 0 && arr[site - 1] > arr[site])
return 0;
return 1;
}
inline void arrprint() {
for (int i = 0; i < k; i++)
printf("%3d", arr[i]);
puts("");
count++;
}
void calculate(int now) {
if (now == k) {
arrprint();
return;
}
for (int i = 0; i < n; i++) {
arr[now] = i;
if (arrsame(now)) {
calculate(now + 1);
}
}
}
inline void run(int nn, int kk) {
n = nn, k = kk;
count = 0;
if (k < 12 && k > 0)
calculate(0);
if (count)
printf("\n%d combination.\n\n", count);
else
puts("Input error!");
}
}
int main() {
int n, k;
while (scanf("%d%d", &n, &k) != EOF) {
re_comb::run(n, k);
fflush(stdout);
}
return 0;
}
推廣
組合數可以推廣到多分類的情形 ,我們將n個物品分為m份,每份的個數分別為:個,那麼,總的分類數為
參見
參考文獻
- ^ 普通高中教科书 数学 选择性必修第三册(A版). 北京市海淀區中關村南大街17號院1號樓: 人民教育出版社. : 23 [2024-03-30]. ISBN 978-7-107-34598-2.
- ^ 組合數學 ─算法與分析─. 九章出版社. : 33. OCLC:44527392
- ^ 3.0 3.1 組合數學 ─算法與分析─. 九章出版社. : 33. OCLC:44527392