组合数与排列数

Question

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

例如，C(10,6) = 210

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

- Rusty

---

请注意，我不是在寻找一个crate，但如果有指向crate的评论仍然很好，例如阶乘crate。 - Rusty

不要忘记使用(1..=n).product()。 - L. F.

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

请注意，有一些微小的优化可以进行，即在 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)
    }
}

- Aplet123

---

这些替换会不会导致整数除法舍入，从而使结果不准确？ - PunkyMunky64

@PunkyMunky64 可以保证，当你除以 val 时，它将是当前累加器的因子，因此不会有不准确性（这就是为什么你要从大到小乘，从小到大除）。 - Aplet123

Answer 2

标准库中没有任何用于计算数字阶乘的运算符或函数。 相反，您可以使用 factorial 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()函数。

- vallentin