跳转到内容

組合

维基百科,自由的百科全书

組合數學,一個的元素的組合(英語:Combination)是一個子集S的一個k-組合是S的一個有k個元素的子集。若兩個子集的元素完全相同並順序相異,它仍視為同一個組合,這是組合和排列不同之處。

表示方式

[编辑]

从 n 个不同元素中取出 k 个元素的所有不同组合的个数,叫做从 n 个不同元素中取出 k 个元素的组合数,记做:(英语)、(法语、罗马尼亚语、俄语、汉语(中國)[1]、波兰语)。

理論與公式

[编辑]

个元素中取出个元素,个元素的组合數量为:

六合彩為例。在六合彩中从49顆球中取出6顆球的组合數量为:

在集合中取出k項元素

[编辑]
在有五個元素中的集合中,取出3個元素,形成的子集合

重複組合理論與公式

[编辑]

个元素中取出个元素,個元素可以重複出現,這组合數量为:

以取色球為例,每種顏色的球有無限多顆,從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]

[编辑]

的定義中,由於它有意義的範圍必須是滿足條件,所以其他範圍必須另外定義,我們有:

[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份,每份的个数分别为:个,那么,总的分类数为

参见

[编辑]

參考文獻

[编辑]
  1. ^ 普通高中教科书 数学 选择性必修第三册(A版). 北京市海淀区中关村南大街17号院1号楼: 人民教育出版社. : 23 [2024-03-30]. ISBN 978-7-107-34598-2. 
  2. ^ 組合數學 ─算法與分析─. 九章出版社. : 33.  OCLC:44527392
  3. ^ 3.0 3.1 組合數學 ─算法與分析─. 九章出版社. : 33.  OCLC:44527392

外部链接

[编辑]