数量 combinations/permutations

Question

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

例如C(10,6) = 210

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

Answer 1

标准库不包含任何用于计算数字阶乘的运算符或函数。

相反，您可以使用 factorial crate or you could use the num crate, which the Rust Cookbook 包含示例。这是 Rust Cookbook 示例的一个变体，没有使用 num crate。

fn factorial(n: u64) -> u64 {
    let mut f = 1;
    for i in 1..=n {
        f *= i;
    }
    f
}

与 , this could be expressed shorter using 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`
}

如果您确实想要生成排列 and/or 组合，那么您可以使用 itertools crate and specifically use the permutations() and combinations() 函数。

Answer 2

根据@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) 而不是 count_combinations 的 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)
    }
}

数量 combinations/permutations

Number of combinations/permutations

rust

combinatorics