Rust算法——阶乘与排列组合——递归与数学算法的 Rust 实现

红目香薰

发布于 2025-12-16 16:36:47

1970

文章被收录于专栏：CSDNToQQCodeCSDNToQQCode

1.2 阶乘与排列组合——递归与数学算法的 Rust 实现

阶乘（Factorial）和排列组合（Permutation & Combination）是数学中的基础概念，也是理解递归算法和数学计算的重要案例。本文将详细介绍如何在 Rust 中实现这些算法，并分析不同实现方式的性能特点。

1. 阶乘（Factorial）

1.1 数学定义

阶乘的数学定义：

n! = n × (n-1) × (n-2) × … × 2 × 1
0! = 1（特殊定义）
1! = 1

示例：

5! = 5 × 4 × 3 × 2 × 1 = 120
10! = 3,628,800

1.2 递归实现

/// 递归实现阶乘
/// 
/// # 参数
/// * `n` - 要计算阶乘的非负整数
/// 
/// # 返回
/// * `Option<u64>` - 阶乘结果，如果溢出则返回 None
/// 
/// # 示例
/// ```
/// assert_eq!(factorial_recursive(5), Some(120));
/// assert_eq!(factorial_recursive(0), Some(1));
/// ```
fn factorial_recursive(n: u32) -> Option<u64> {
    match n {
        0 | 1 => Some(1),
        _ => {
            let prev = factorial_recursive(n - 1)?;
            prev.checked_mul(n as u64)
        }
    }
}

fn main() {
    for i in 0..=10 {
        match factorial_recursive(i) {
            Some(result) => println!("{}! = {}", i, result),
            None => println!("{}! = 溢出", i),
        }
    }
}

特点：

✅ 代码简洁，符合数学定义
⚠️ 递归深度为 n，可能栈溢出
⚠️ 对于大数可能溢出

1.3 迭代实现（推荐）

/// 迭代实现阶乘（推荐）
/// 
/// 使用循环而非递归，避免栈溢出问题
fn factorial_iterative(n: u32) -> Option<u64> {
    match n {
        0 | 1 => Some(1),
        _ => {
            let mut result = 1u64;
            for i in 2..=n {
                result = result.checked_mul(i as u64)?;
            }
            Some(result)
        }
    }
}

fn main() {
    println!("迭代实现阶乘：");
    for i in 0..=20 {
        match factorial_iterative(i) {
            Some(result) => println!("{}! = {}", i, result),
            None => println!("{}! = 溢出", i),
        }
    }
}

优势：

✅ 无递归调用，不会栈溢出
✅ 性能更好（无函数调用开销）
✅ 使用 checked_mul 防止溢出

1.4 使用迭代器实现

/// 使用 Rust 迭代器实现阶乘
fn factorial_iterator(n: u32) -> Option<u64> {
    match n {
        0 | 1 => Some(1),
        _ => (2..=n)
            .map(|x| x as u64)
            .try_fold(1u64, |acc, x| acc.checked_mul(x))
    }
}

fn main() {
    println!("迭代器实现阶乘：");
    for i in 0..=15 {
        match factorial_iterator(i) {
            Some(result) => println!("{}! = {}", i, result),
            None => println!("{}! = 溢出", i),
        }
    }
}

特点：

✅ 函数式编程风格
✅ 利用 Rust 迭代器的零成本抽象
✅ 代码简洁优雅

1.5 大数阶乘（使用大整数）

对于超过 u64 范围的阶乘，需要使用大整数库：

// 需要添加依赖：num-bigint
// Cargo.toml: num-bigint = "0.4"

use num_bigint::BigUint;
use num_traits::One;

fn factorial_bigint(n: u32) -> BigUint {
    match n {
        0 | 1 => BigUint::one(),
        _ => {
            let mut result = BigUint::one();
            for i in 2..=n {
                result *= BigUint::from(i);
            }
            result
        }
    }
}

fn main() {
    println!("大数阶乘：");
    for i in 0..=30 {
        println!("{}! = {}", i, factorial_bigint(i));
    }
    
    // 计算 100!
    println!("\n100! = {}", factorial_bigint(100));
}

2. 排列（Permutation）

2.1 数学定义

从 n 个不同元素中取出 m 个元素（m ≤ n），按照一定顺序排成一列，称为排列。

排列数公式：

P(n, m) = n! / (n - m)!
P(n, n) = n!（全排列）

示例：

P(5, 3) = 5! / 2! = 5 × 4 × 3 = 60
从 {1, 2, 3} 中取 2 个的排列：12, 13, 21, 23, 31, 32（共 6 种）

2.2 计算排列数

/// 计算排列数 P(n, m) = n! / (n - m)!
fn permutation_count(n: u32, m: u32) -> Option<u64> {
    if m > n {
        return Some(0);
    }
    if m == 0 {
        return Some(1);
    }
    
    // 优化：P(n, m) = n × (n-1) × ... × (n-m+1)
    // 避免计算完整的阶乘
    let mut result = 1u64;
    for i in (n - m + 1)..=n {
        result = result.checked_mul(i as u64)?;
    }
    Some(result)
}

fn main() {
    println!("排列数计算：");
    println!("P(5, 3) = {:?}", permutation_count(5, 3));  // 60
    println!("P(10, 4) = {:?}", permutation_count(10, 4)); // 5040
    println!("P(5, 0) = {:?}", permutation_count(5, 0));   // 1
    println!("P(5, 6) = {:?}", permutation_count(5, 6));   // 0
}

2.3 生成所有排列（回溯算法）

/// 生成从 n 个元素中取 m 个的所有排列
fn generate_permutations(n: u32, m: u32) -> Vec<Vec<u32>> {
    if m > n || m == 0 {
        return vec![];
    }
    
    let mut result = Vec::new();
    let mut current = Vec::new();
    let mut used = vec![false; n as usize];
    
    fn backtrack(
        n: u32,
        m: u32,
        current: &mut Vec<u32>,
        used: &mut Vec<bool>,
        result: &mut Vec<Vec<u32>>,
    ) {
        if current.len() == m as usize {
            result.push(current.clone());
            return;
        }
        
        for i in 0..n {
            if !used[i as usize] {
                used[i as usize] = true;
                current.push(i);
                backtrack(n, m, current, used, result);
                current.pop();
                used[i as usize] = false;
            }
        }
    }
    
    backtrack(n, m, &mut current, &mut used, &mut result);
    result
}

fn main() {
    println!("生成排列：");
    let perms = generate_permutations(3, 2);
    for perm in &perms {
        println!("{:?}", perm);
    }
    println!("共 {} 种排列", perms.len());
}

输出：

生成排列：
[0, 1]
[0, 2]
[1, 0]
[1, 2]
[2, 0]
[2, 1]
共 6 种排列

2.4 生成全排列

/// 生成 n 个元素的全排列
fn generate_all_permutations(n: u32) -> Vec<Vec<u32>> {
    generate_permutations(n, n)
}

/// 使用 Rust 迭代器生成排列（更高效）
fn permutations_iterator<T: Clone>(items: Vec<T>, k: usize) -> Vec<Vec<T>> {
    if k == 0 {
        return vec![vec![]];
    }
    if k > items.len() {
        return vec![];
    }
    
    let mut result = Vec::new();
    for i in 0..items.len() {
        let mut remaining = items.clone();
        let item = remaining.remove(i);
        for mut perm in permutations_iterator(remaining, k - 1) {
            perm.insert(0, item.clone());
            result.push(perm);
        }
    }
    result
}

fn main() {
    println!("全排列示例：");
    let items = vec!['A', 'B', 'C'];
    let perms = permutations_iterator(items, 3);
    for perm in &perms {
        println!("{:?}", perm);
    }
}

3. 组合（Combination）

3.1 数学定义

从 n 个不同元素中取出 m 个元素（m ≤ n），不考虑顺序，称为组合。

组合数公式：

C(n, m) = n! / (m! × (n - m)!)
C(n, m) = C(n, n - m)（对称性）
C(n, 0) = C(n, n) = 1

示例：

C(5, 3) = 5! / (3! × 2!) = 10
从 {1, 2, 3, 4, 5} 中取 3 个的组合：{1,2,3}, {1,2,4}, {1,2,5}, {1,3,4}, {1,3,5}, {1,4,5}, {2,3,4}, {2,3,5}, {2,4,5}, {3,4,5}（共 10 种）

3.2 计算组合数

/// 计算组合数 C(n, m) = n! / (m! × (n - m)!)
fn combination_count(n: u32, m: u32) -> Option<u64> {
    if m > n {
        return Some(0);
    }
    if m == 0 || m == n {
        return Some(1);
    }
    
    // 优化：利用对称性 C(n, m) = C(n, n-m)
    let m = m.min(n - m);
    
    // 优化：C(n, m) = (n × (n-1) × ... × (n-m+1)) / (m × (m-1) × ... × 1)
    let mut numerator = 1u64;
    let mut denominator = 1u64;
    
    for i in 0..m {
        numerator = numerator.checked_mul((n - i) as u64)?;
        denominator = denominator.checked_mul((m - i) as u64)?;
    }
    
    Some(numerator / denominator)
}

fn main() {
    println!("组合数计算：");
    println!("C(5, 3) = {:?}", combination_count(5, 3));   // 10
    println!("C(10, 4) = {:?}", combination_count(10, 4)); // 210
    println!("C(5, 0) = {:?}", combination_count(5, 0));   // 1
    println!("C(5, 5) = {:?}", combination_count(5, 5));   // 1
    println!("C(5, 6) = {:?}", combination_count(5, 6));   // 0
}

3.3 生成所有组合（回溯算法）

/// 生成从 n 个元素中取 m 个的所有组合
fn generate_combinations(n: u32, m: u32) -> Vec<Vec<u32>> {
    if m > n || m == 0 {
        return vec![];
    }
    
    let mut result = Vec::new();
    let mut current = Vec::new();
    
    fn backtrack(
        start: u32,
        n: u32,
        m: u32,
        current: &mut Vec<u32>,
        result: &mut Vec<Vec<u32>>,
    ) {
        if current.len() == m as usize {
            result.push(current.clone());
            return;
        }
        
        // 组合不需要考虑顺序，所以从 start 开始，避免重复
        for i in start..n {
            current.push(i);
            backtrack(i + 1, n, m, current, result);
            current.pop();
        }
    }
    
    backtrack(0, n, m, &mut current, &mut result);
    result
}

fn main() {
    println!("生成组合：");
    let combs = generate_combinations(5, 3);
    for comb in &combs {
        println!("{:?}", comb);
    }
    println!("共 {} 种组合", combs.len());
}

输出：

生成组合：
[0, 1, 2]
[0, 1, 3]
[0, 1, 4]
[0, 2, 3]
[0, 2, 4]
[0, 3, 4]
[1, 2, 3]
[1, 2, 4]
[1, 3, 4]
[2, 3, 4]
共 10 种组合

3.4 使用迭代器生成组合

/// 使用迭代器生成组合（更函数式）
fn combinations_iterator<T: Clone>(items: Vec<T>, k: usize) -> Vec<Vec<T>> {
    if k == 0 {
        return vec![vec![]];
    }
    if k > items.len() {
        return vec![];
    }
    
    let mut result = Vec::new();
    for i in 0..=items.len() - k {
        let item = items[i].clone();
        for mut comb in combinations_iterator(items[i + 1..].to_vec(), k - 1) {
            comb.insert(0, item.clone());
            result.push(comb);
        }
    }
    result
}

fn main() {
    println!("组合示例：");
    let items = vec!['A', 'B', 'C', 'D'];
    let combs = combinations_iterator(items, 2);
    for comb in &combs {
        println!("{:?}", comb);
    }
    println!("共 {} 种组合", combs.len());
}

4. 性能对比与优化

4.1 阶乘性能对比

use std::time::Instant;

fn benchmark_factorial() {
    let n = 20;
    
    // 测试递归实现
    let start = Instant::now();
    let _ = factorial_recursive(n);
    let recursive_time = start.elapsed();
    
    // 测试迭代实现
    let start = Instant::now();
    let _ = factorial_iterative(n);
    let iterative_time = start.elapsed();
    
    // 测试迭代器实现
    let start = Instant::now();
    let _ = factorial_iterator(n);
    let iterator_time = start.elapsed();
    
    println!("阶乘性能对比（n = {}）：", n);
    println!("递归实现: {:?}", recursive_time);
    println!("迭代实现: {:?}", iterative_time);
    println!("迭代器实现: {:?}", iterator_time);
}

性能特点：

迭代实现：最快，无函数调用开销
迭代器实现：接近迭代实现，代码更优雅
递归实现：较慢，有函数调用开销和栈风险

4.2 排列组合性能优化

/// 优化的组合数计算（使用动态规划避免重复计算）
fn combination_count_dp(n: u32, m: u32) -> Option<u64> {
    if m > n {
        return Some(0);
    }
    if m == 0 || m == n {
        return Some(1);
    }
    
    // 使用帕斯卡三角形（杨辉三角）计算
    // C(n, m) = C(n-1, m-1) + C(n-1, m)
    let m = m.min(n - m) as usize;
    let mut dp = vec![0u64; m + 1];
    dp[0] = 1;
    
    for i in 1..=n as usize {
        for j in (1..=m.min(i)).rev() {
            dp[j] = dp[j].checked_add(dp[j - 1])?;
        }
    }
    
    Some(dp[m])
}

fn main() {
    println!("组合数计算对比：");
    let n = 50;
    let m = 25;
    
    let start = Instant::now();
    let result1 = combination_count(n, m);
    let time1 = start.elapsed();
    
    let start = Instant::now();
    let result2 = combination_count_dp(n, m);
    let time2 = start.elapsed();
    
    println!("直接计算: {:?}, 结果: {:?}", time1, result1);
    println!("动态规划: {:?}, 结果: {:?}", time2, result2);
}

5. 实际应用示例

5.1 计算概率

/// 计算从 n 个元素中随机取 m 个，包含特定 k 个元素的概率
fn probability_contains(n: u32, m: u32, k: u32) -> Option<f64> {
    if k > m || m > n {
        return None;
    }
    
    // 概率 = C(n-k, m-k) / C(n, m)
    let numerator = combination_count(n - k, m - k)?;
    let denominator = combination_count(n, m)?;
    
    Some(numerator as f64 / denominator as f64)
}

fn main() {
    // 从 52 张牌中取 5 张，包含 2 张 A 的概率
    let prob = probability_contains(52, 5, 2);
    println!("概率: {:?}", prob);
}

5.2 生成密码组合

/// 生成指定长度的密码组合
fn generate_password_combinations(chars: Vec<char>, length: usize) -> Vec<String> {
    let perms = generate_permutations(chars.len() as u32, length as u32);
    perms.into_iter()
        .map(|indices| {
            indices.iter()
                .map(|&i| chars[i as usize])
                .collect::<String>()
        })
        .collect()
}

fn main() {
    let chars = vec!['a', 'b', 'c', 'd'];
    let passwords = generate_password_combinations(chars, 3);
    println!("可能的密码组合：");
    for pwd in passwords {
        println!("{}", pwd);
    }
}

5.3 组合优化问题

/// 从 n 个物品中选择 m 个，使得总价值最大
fn knapsack_combination(
    items: &[(u32, u32)], // (重量, 价值)
    capacity: u32,
    count: usize,
) -> Option<(Vec<usize>, u32)> {
    let n = items.len();
    if count > n {
        return None;
    }
    
    let combs = generate_combinations(n as u32, count as u32);
    let mut best_value = 0;
    let mut best_combination = None;
    
    for comb in combs {
        let total_weight: u32 = comb.iter().map(|&i| items[i as usize].0).sum();
        if total_weight <= capacity {
            let total_value: u32 = comb.iter().map(|&i| items[i as usize].1).sum();
            if total_value > best_value {
                best_value = total_value;
                best_combination = Some(comb);
            }
        }
    }
    
    best_combination.map(|comb| (comb.into_iter().map(|x| x as usize).collect(), best_value))
}

fn main() {
    let items = vec![(10, 60), (20, 100), (30, 120)];
    let result = knapsack_combination(&items, 50, 2);
    println!("最优组合: {:?}", result);
}

6. 扩展练习

练习 1：实现阶乘的尾递归优化

尝试将递归阶乘改为尾递归形式，减少栈空间使用。

练习 2：计算排列组合的模运算

对于大数，计算 C(n, m) mod p，其中 p 是质数。

练习 3：生成带重复元素的排列

实现生成有重复元素的排列，如 [1, 1, 2] 的排列。

练习 4：实现组合的迭代器版本

使用 Rust 迭代器实现一个惰性求值的组合生成器。

练习 5：计算多重集合的组合

从有重复元素的集合中选择元素的组合数。

总结

通过本章学习，你应该掌握：

✅ 阶乘的多种实现方式（递归、迭代、迭代器） ✅ 排列数的计算和生成 ✅ 组合数的计算和生成 ✅ 回溯算法的应用 ✅ 性能优化技巧 ✅ 实际应用场景

关键要点：

递归适合理解，迭代适合性能
使用 checked_mul 等检查方法防止溢出
回溯算法是生成排列组合的经典方法
Rust 迭代器提供零成本抽象

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-11-07，如有侵权请联系 cloudcommunity@tencent.com 删除

算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度