如何实现大数求组合

C(10000,3) 如何实现

n个互不相同的数的全排列是n！个。

一个有n个元素的集合的含有m个元素子集的个数为C(n,m)。

C(n,m)的计算方式：

1.公式：C(n,m) = n!/((n-m)! * m!)，在算法上较难实现，阶乘很快会爆

2.递推：C(n,m) = C(n-1,m-1) + C(n-1,m)

代码

下面代码是递推的实现

func C(n, m int) int {
	data := make([][]int, n+1)
	for i := range data {
		data[i] = make([]int, m+1)
	}
	c(data, n, m)
	return data[n][m]
}

// 公式：c(n,m)=c(n-1,m-1)+c(n-1,m)
func c(data [][]int, n, m int) {
	if m > n {
		return
	}

	if n == 0 {
		data[n][m] = 0
		return
	}

	if m == 0 {
		data[n][m] = 1
		return
	}

	if n == 1 {
		data[n][m] = 1
		return
	}

	if m == 1 {
		data[n][m] = n
		return
	}

	c(data, n-1, m-1)
	c(data, n-1, m)
	data[n][m] = data[n-1][m-1] + data[n-1][m]
}

测试

func main() {
	testCases := []struct {
		m, n, want int
	}{
		{0, 0, 0},
		{0, 1, 1},
		{0, 2, 1},
		{1, 0, 0},
		{1, 1, 1},
		{1, 2, 2},
		{2, 2, 1},
		{0, 3, 1},
		{1, 3, 3},
		{2, 3, 3},
		{3, 3, 1},
		{0, 4, 1},
		{1, 4, 4},
		{2, 4, 6},
		{3, 4, 4},
		{4, 4, 1},
		{0, 5, 1},
		{1, 5, 5},
		{2, 5, 10},
		{3, 5, 10},
		{4, 5, 5},
		{5, 5, 1},
		{3, 10000, 166616670000},
	}
	for _, testCase := range testCases {
		actural := C(testCase.n, testCase.m)
		if actural != testCase.want {
			fmt.Printf("n:%d,m:%d,want:%d,actual:%d\n", testCase.n, testCase.m, testCase.want, actural)
		}
	}
}

递推公式有个缺点就是特别慢，因为它要先计算出前面c(n,m)前面所有的组合。

如果直接用公式就非常快了，各有优缺点。

参考文档中[1]中介绍了一种数学推演法，比较难理解，对代数要求比较高，感兴趣的同学可以研究一下。

参考

[1]组合数C(n,m)的计算