rust - 组合/排列的数量

Question

如何在 rust 中找到排列或组合的数量？

例如C(10,6) = 210

我在标准库中找不到这个函数，也找不到那里的阶乘运算符(这就足够了)。

Answer 1

以@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)
    }
}