如何正确的实现一个计算组合数函数

计算组合数(Combination) C(n, k)的数学公式为 n! / ( k! * (n-k)! ), !表示阶乘(Factorial)的。 按公式很容易理解:分别求出三个阶乘数,然后再做两次除法操作即可得到组合数。

实现一:

func F(n int) int {
	if n == 1 {
		return 1
	}
	return n*F(n-1)
}

func C(n, k int) int {
	return F(n) / F(k) / F(n-k)
}

但是,实现一的问题是在求阶乘时可能出现整数溢出。以64位机器为例,uint64的最大值为18446744073709551615, 21的阶乘为51090942171709440000,溢出了。按这种方式计算,最大可以求出n=20的组合数。

实现二:

// Gcd : calculate greatest common divisor by Euclidean algorithm
func Gcd(a, b int) int {
	if b == 0 {
		return a
	}
	return Gcd(b, a%b)
}

// Div : divide by gcd
func Div(a, b int) (a0, b0 int) {
	gcd := Gcd(a, b)
	a /= gcd
	b /= gcd
	return a, b
}

// C : combination (k <= n), prevent overflow
func C(n, k int) int {
	i := k + 1
	r := n - k
	if r > k {
		i = r + 1
		r = k
	}
	f1, f2 := 1, 1
	j := 1
	for ; i <= n; i++ {
		f1 *= i
		for ; j <= r; j++ {
			f2 *= j
			if f2 > f1 {
				j++
				break
			}
			if gcd := Gcd(f1, f2); gcd > 1 {
				f1, f2 = Div(f1, f2)
			}
		}
	}
	return f1 / f2
}

实现二通过不断约化(通过欧几里得算法求最大公约数求约)结果来防止溢出,这种方法大大提高了可以计算出的组合数上限,理论上限为最大的int值。

在很多应用场景,实现二应该可以满足需求。如果要得到一个通用的实现,需要引入大数计算,Go语言中有math/big包可以使用。

Contents