Rust递归生成无重复固定长度a-z字符组合的优化实现咨询

问题描述 #

需要生成a-z范围内所有无重复、固定长度的字符排列。例如限定字符集为a-f、长度为3时，结果包含abc、abd、abe、abf、acb等所有排列组合。

原递归实现通过频繁克隆字符串完成，因所有权规则限制导致效率极低，希望手动实现高效版本。

原实现代码：

fn main() {
    run(&String::new());
}

fn run(target: &String) {
    for a in 97..123 { // ASCII a..z
        if !target.contains(char::from(a)) {
            let next = target.clone() + char::from(a).to_string().as_str(); // Working but terrible
            if next.len() == 3 { // Required string size
                println!("{}", next);
            } else {
                run(&next);
            }
        }
    }
}

原代码的性能瓶颈 #

1. 频繁字符串克隆：每次递归都要克隆当前字符串并追加新字符，String的克隆是深拷贝，随着递归深度增加，拷贝的数据量越来越大，累积开销极高。
2. 低效的重复检查：用String::contains判断字符是否已使用，时间复杂度为O(n)（n为当前字符串长度），进一步拖慢性能。

高效实现思路 #

核心优化点：

• 用轻量中间结构替代字符串克隆：用栈分配的数组或Vec保存当前路径的字符，仅在达到目标长度时才生成最终字符串。
• 位掩码快速检查重复：利用a-z共26个字符的特性，用一个u32的二进制位标记已使用的字符，检查操作时间复杂度降为O(1)。
• 回溯复用内存：递归回溯时仅需弹出最后一个字符、清除对应位掩码，无额外内存分配。

优化版本1：基于Vec和位掩码的递归实现 #

fn main() {
    const TARGET_LENGTH: usize = 3;
    let mut current_chars = Vec::with_capacity(TARGET_LENGTH);
    let mut used_mask = 0u32;
    generate_permutations(TARGET_LENGTH, &mut current_chars, &mut used_mask);
}

fn generate_permutations(target_len: usize, current: &mut Vec<char>, used: &mut u32) {
    // 达到目标长度，生成字符串并输出
    if current.len() == target_len {
        println!("{}", current.iter().collect::<String>());
        return;
    }

    for c_byte in b'a'..=b'z' {
        let char_index = c_byte - b'a';
        let mask = 1 << char_index;
        // 检查当前字符是否未被使用
        if (*used & mask) == 0 {
            // 标记字符为已使用
            *used |= mask;
            current.push(c_byte as char);
            // 递归生成下一层
            generate_permutations(target_len, current, used);
            // 回溯：取消标记并移除当前字符
            current.pop();
            *used &= !mask;
        }
    }
}

优化版本2：固定大小数组的零分配实现 #

如果目标长度固定，可以用栈分配的固定大小数组替代Vec，完全避免动态内存分配：

fn main() {
    const TARGET_LENGTH: usize = 3;
    let mut current_chars = ['\0'; TARGET_LENGTH];
    let mut used_mask = 0u32;
    generate_fixed_permutations(0, TARGET_LENGTH, &mut current_chars, &mut used_mask);
}

fn generate_fixed_permutations(
    current_pos: usize,
    target_len: usize,
    current: &mut [char; 3],
    used: &mut u32
) {
    if current_pos == target_len {
        println!("{}", current.iter().collect::<String>());
        return;
    }

    for c_byte in b'a'..=b'z' {
        let char_index = c_byte - b'a';
        let mask = 1 << char_index;
        if (*used & mask) == 0 {
            *used |= mask;
            current[current_pos] = c_byte as char;
            generate_fixed_permutations(current_pos + 1, target_len, current, used);
            *used &= !mask;
        }
    }
}

性能对比 #

• 原实现：每个排列需要O(n)次字符串克隆（n为目标长度），重复检查O(n)，总时间复杂度O(n * P(26, n))（P为排列数）。
• 优化实现：仅在输出时做一次字符串转换，重复检查O(1)，总时间复杂度O(P(26, n))，内存开销仅为栈上的数组/Vec和一个u32变量，性能提升显著。

内容的提问来源于stack exchange，提问作者Cirrocumulus