在Rust中构造修改版幂集：筛选符合特定规则的子集

核心结论 #

分阶段构造（思路2）的效率远高于朴素筛选（思路1），尤其是当输入规模增大时——输入的特性（每个二元组恰好有一个同第二元素的伙伴）让我们可以拆解问题为分组选择，彻底避免生成大量无效子集。

问题本质 #

输入的约束等价于：每个第二元素在子集中最多出现一次。结合输入特性（每个第二元素对应恰好两个二元组），我们可以将输入按第二元素拆分为若干二元组对。此时符合约束的子集就是对每个组选择「不选任何元素」「选第一个元素」「选第二个元素」三者之一的组合，总有效子集数为3^k（k为分组数），而普通幂集的子集数是2^(2k)，两者差距随k增大呈指数级扩大。

具体实现步骤 #

1. 预处理分组：将输入的二元组按第二元素分组，利用输入特性保证每组恰好包含两个元素。
2. 迭代构造子集：从空集开始，对每个分组扩展现有子集，生成三种合法的新子集，最终得到所有符合约束的结果。

Rust代码实现 #

use std::collections::HashMap;
use std::hash::Hash;

// 按第二元素分组，返回每组的两个二元组引用
fn group_pairs<T: Eq + Hash, U: Eq + Hash>(pairs: &[(T, U)]) -> Vec<(&T, &U), (&T, &U)> {
    let mut group_map = HashMap::new();
    for pair in pairs {
        group_map.entry(&pair.1).or_insert_with(Vec::new).push(pair);
    }
    // 输入保证每组恰好两个元素，unwrap安全
    group_map.into_values()
        .map(|mut group| (group.remove(0), group.remove(0)))
        .collect()
}

// 生成符合约束的幂集，所有元素均为原输入的引用
fn modified_power_set<T: Eq + Hash, U: Eq + Hash>(pairs: &[(T, U)]) -> Vec<Vec<&(T, U)>> {
    let groups = group_pairs(pairs);
    let mut result = vec![vec![]]; // 初始空集

    for &(a, b) in &groups {
        let mut new_subsets = Vec::with_capacity(result.len() * 3);
        for subset in &result {
            // 1. 不添加当前组的任何元素
            new_subsets.push(subset.clone());
            // 2. 添加组内第一个元素
            let mut with_a = subset.clone();
            with_a.push(a);
            new_subsets.push(with_a);
            // 3. 添加组内第二个元素
            let mut with_b = subset.clone();
            with_b.push(b);
            new_subsets.push(with_b);
        }
        result = new_subsets;
    }

    result
}

// 示例测试
fn main() {
    let input = [('a', 'b'), ('c', 'b')];
    let power_set = modified_power_set(&input);
    
    // 输出：[[], [('a', 'b')], [('c', 'b')]]
    for subset in power_set {
        println!("{:?}", subset);
    }
}

效率对比 #

• 时间复杂度：预处理为O(n)（n为输入元素数），构造阶段为O(3^k)（k = n/2）。而思路1的时间复杂度是O(2^n * n)（生成所有子集后逐个检查约束），当n=20时，3^10=59049 vs 2^20=1048576，前者计算量仅为后者的5.6%；当n=40时，差距扩大到0.35%。
• 内存占用：思路2仅需存储3^k个子集，而思路1需要存储2^n个子集，内存差距同样呈指数级。
• 分配优化：所有子集元素均为原输入的引用，无额外数据复制，完全符合你的需求。

何时考虑思路1 #

只有当输入规模极小（比如k<=2，即n<=4）时，思路1的代码简洁性可能略占优势，但对于绝大多数场景，思路2是更高效、更惯用的选择。

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