深入理解斯特林数（Stirling Numbers）

什么是斯特林数？

斯特林数分为两类：

• 第一类斯特林数（记作 s(n, k) 或 c(n, k)）：表示将 n 个不同元素排成 k 个非空循环排列的方式数。
• 第二类斯特林数（记作 S(n, k)）：表示将 n 个不同元素划分为 k 个非空无序子集的方式数。

本文重点讲解 第二类斯特林数，因为它在实际应用中更为常见，例如在聚类分析、概率论和动态规划中都有广泛应用。

递推关系

第二类斯特林数满足如下递推公式：

S(n, k) = k × S(n−1, k) + S(n−1, k−1)

边界条件为：

• S(0, 0) = 1
• S(n, 0) = 0 （当 n > 0）
• S(0, k) = 0 （当 k > 0）
• S(n, k) = 0 （当 k > n）

用 Rust 实现第二类斯特林数

我们将使用 动态规划 方法来高效计算斯特林数。以下是完整的 Rust 代码实现：

fn stirling_second_kind(n: usize, k: usize) -> usize {    // 处理边界情况    if k == 0 {        return if n == 0 { 1 } else { 0 };    }    if n == 0 || k > n {        return 0;    }    // 创建二维 DP 表    let mut dp = vec![vec![0; k + 1]; n + 1];        // 初始化边界条件    dp[0][0] = 1;        // 填充 DP 表    for i in 1..=n {        for j in 1..=std::cmp::min(i, k) {            dp[i][j] = j * dp[i - 1][j] + dp[i - 1][j - 1];        }    }        dp[n][k]}fn main() {    // 测试几个例子    println!("S(3, 2) = {}", stirling_second_kind(3, 2)); // 应输出 3    println!("S(4, 2) = {}", stirling_second_kind(4, 2)); // 应输出 7    println!("S(5, 3) = {}", stirling_second_kind(5, 3)); // 应输出 25}

这段代码清晰地展示了如何使用 Rust 的 vec! 宏创建动态数组，并通过嵌套循环填充动态规划表。时间复杂度为 O(n×k)，空间复杂度也为 O(n×k)。

优化空间复杂度

如果你只关心最终结果而不需要保存整个表格，可以将空间复杂度优化到 O(k)。以下是优化后的版本：

fn stirling_second_kind_optimized(n: usize, k: usize) -> usize {    if k == 0 {        return if n == 0 { 1 } else { 0 };    }    if n == 0 || k > n {        return 0;    }    let mut prev = vec![0; k + 1];    let mut curr = vec![0; k + 1];    prev[0] = 1;    for i in 1..=n {        curr[0] = 0;        for j in 1..=std::cmp::min(i, k) {            curr[j] = j * prev[j] + prev[j - 1];        }        std::mem::swap(&mut prev, &mut curr);    }    prev[k]}

为什么学习 Rust 实现斯特林数？

掌握 Rust 斯特林数 算法不仅能加深你对组合数学的理解，还能提升你在 Rust 编程教程 中处理递归与动态规划问题的能力。Rust 的内存安全特性确保你的算法不会出现空指针或缓冲区溢出等常见错误，非常适合教学和工业级应用。

此外，斯特林数算法 是许多高级算法（如贝尔数计算、集合划分问题）的基础。通过本教程，你已经掌握了用 组合数学 Rust 实现核心数学工具的关键技能。

总结

本文详细介绍了斯特林数的概念、递推关系，并提供了两种 Rust 实现方式：基础版和空间优化版。你可以将这些代码直接用于项目或进一步扩展（例如添加缓存、支持大整数等）。

希望这篇 Rust 语言斯特林数算法 教程对你有帮助！动手试试吧，修改参数、添加测试用例，让学习过程更有趣。