最佳答案
以@vallentin 的回答为基础,可以进行许多优化。让我们使用相同的阶乘函数(现在):
fn factorial(n: u64) -> u64 {
(1..=n).product()
}
对于 count_permutations
,n!/(n - r)!
实际上只是 n - r + 1
和 n
(含)之间所有数字的乘积,所以我们不甚至需要计算 2 个阶乘(这可能会溢出并涉及计算重叠数字的乘积):
fn count_permutations(n: u64, r: u64) -> u64 {
(n - r + 1..=n).product()
}
我们可以对count_combinations
做类似的优化:
fn count_combinations(n: u64, r: u64) -> u64 {
(n - r + 1..=n).product::<u64>() / factorial(r)
}
count_permutations
几乎完全优化,既快速又正确(如果 count_permutations
的结果可以适合 u64
那么它应该永不溢出)。
count_combinations
仍然存在一些缺陷,即由于它是计算乘积然后除法,其结果可以适合 u64
,但函数仍会溢出。您可以通过交替乘法和除法使其非常接近非溢出:
fn count_combinations(n: u64, r: u64) -> u64 {
if r > n {
0
} else {
(1..=r).fold(1, |acc, val| acc * (n - val + 1) / val)
}
}
把它们放在一起:
fn count_combinations(n: u64, r: u64) -> u64 {
if r > n {
0
} else {
(1..=r).fold(1, |acc, val| acc * (n - val + 1) / val)
}
}
fn count_permutations(n: u64, r: u64) -> u64 {
(n - r + 1..=n).product()
}
fn main() {
println!("{}", count_combinations(10, 6));
println!("{}", count_permutations(10, 6));
}
请注意,您可以进行一些微优化,即使用 r.min(n - r)
而不是 r
获得 count_combinations
,由于 count_combinations(n, r) == count_combinations(n, n - r)
,并且选择两者中较小的一个将缩小循环大小:
fn count_combinations(n: u64, r: u64) -> u64 {
if r > n {
0
} else {
(1..=r.min(n - r)).fold(1, |acc, val| acc * (n - val + 1) / val)
}
}
关于rust - 组合/排列的数量,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/65561566/