我该如何在rust中找到排列或组合的数量?
我在标准库中找不到这个函数,也找不到阶乘运算符(它足够使用)。
在 @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));
}
请注意,有一些微小的优化可以进行,即在 count_combinations
中使用 r.min(n - r)
而不是 r
,因为 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)
}
}
val
时,它将是当前累加器的因子,因此不会有不准确性(这就是为什么你要从大到小乘,从小到大除)。 - Aplet123factorial
crate 或 num
crate,其中 Rust Cookbook 包括一个示例。这是 Rust Cookbook 示例的一个变体,不使用 num
crate。
fn factorial(n: u64) -> u64 {
let mut f = 1;
for i in 1..=n {
f *= i;
}
f
}
正如L. F.所评论的那样,这可以使用product()
更短地表达,product()
的文档中包含了一个示例。
fn factorial(n: u64) -> u64 {
(1..=n).product()
}
n
和 r
的排列数或组合数的函数。相反,您可以将公式转换为函数,如下所示:
/// n! / (r! * (n - r)!)
fn count_combinations(n: u64, r: u64) -> u64 {
factorial(n) / (factorial(r) * factorial(n - r))
}
/// n! / (n - r)!
fn count_permutations(n: u64, r: u64) -> u64 {
factorial(n) / factorial(n - r)
}
fn main() {
println!("{}", count_combinations(10, 6)); // Prints `210`
println!("{}", count_permutations(10, 6)); // Prints `151200`
}
如果你想要生成排列和/或组合,那么你可以使用itertools
crate,并具体使用permutations()
和combinations()
函数。
(1..=n).product()
。 - L. F.