组合/排列的数量

Question

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

例如C(10,6) = 210

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

Answer 1

Building off @vallentin's answer, there are many optimizations that could be made. Let's use the same factorial function (for now):

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可以适合 au64那么它永远不会溢出）。

count_combinations仍然有一些缺陷，即由于它先计算乘积然后除法，所以它的结果可以适合 a u64，但该函数仍然会溢出。您可以通过交替乘法和除法使其非常接近非溢出：

fn count_combinations(n: u64, r: u64) -> u64 {
    (n - r + 1..=n).product::<u64>() / factorial(r)
}

把它们放在一起：

fn count_combinations(n: u64, r: u64) -> u64 {
    if r > n {
        0
    } else {
        (1..=r).fold(1, |acc, val| acc * (n - val + 1) / val)
    }
}

请注意，您可以进行一些微观优化，即使用for 、sincer.min(n - r)来代替，并使用两者中较小的一个来缩小循环大小：rcount_combinationscount_combinations(n, r) == count_combinations(n, n - r)

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));
}