Rust中生成n个不重复随机数的高效方法（括号校验测试场景）

分场景优化实现 #

当N ≈ n（即N = n + ε）时

直接采用你提到的第一种思路，生成0到N的索引向量并打乱，取前n个即可。这种场景下N和n规模接近，O(N)的时间开销完全可接受。

use rand::seq::SliceRandom;
use rand::thread_rng;

fn generate_indices_dense(n: usize, N: usize) -> Vec<usize> {
    let mut indices: Vec<usize> = (0..N).collect();
    let mut rng = thread_rng();
    indices.shuffle(&mut rng);
    indices.into_iter().take(n).collect()
}

当N >> n时

用你提到的第二种思路，借助HashSet收集不重复随机数。由于n远小于N，碰撞概率极低，效率很高。提前指定HashSet的容量还能进一步减少内存分配开销。

use rand::Rng;
use std::collections::HashSet;

fn generate_indices_sparse(n: usize, N: usize) -> Vec<usize> {
    let mut rng = rand::thread_rng();
    let mut set = HashSet::with_capacity(n);
    while set.len() < n {
        let num = rng.gen_range(0..N);
        set.insert(num);
    }
    set.into_iter().collect()
}

自适应通用方案 #

可以写一个自动适配场景的函数，根据N和n的比例选择最优策略——当n超过N的一半时用打乱法，否则用HashSet收集，兼顾两种场景的效率：

use rand::seq::SliceRandom;
use rand::Rng;
use std::collections::HashSet;

fn generate_indices_adaptive(n: usize, N: usize) -> Vec<usize> {
    assert!(n <= N, "n cannot be larger than N");
    let mut rng = rand::thread_rng();
    
    if n * 2 > N {
        let mut indices: Vec<usize> = (0..N).collect();
        indices.shuffle(&mut rng);
        indices.into_iter().take(n).collect()
    } else {
        let mut set = HashSet::with_capacity(n);
        while set.len() < n {
            let num = rng.gen_range(0..N);
            set.insert(num);
        }
        set.into_iter().collect()
    }
}

额外：生成合法括号字符串 #

拿到不重复索引后，只需将索引排序，前半部分放左括号、后半部分放右括号，就能保证括号的合法性：

fn generate_valid_bracket_string(N: usize, n: usize) -> String {
    assert!(n % 2 == 0, "n must be even for valid brackets");
    // 用'0'作为默认非括号字符，可替换为你需要的任意数字
    let mut chars = vec!['0'; N];
    let indices = generate_indices_adaptive(n, N);
    let mut sorted_indices = indices;
    sorted_indices.sort_unstable();
    
    for &idx in sorted_indices.iter().take(n/2) {
        chars[idx] = '(';
    }
    for &idx in sorted_indices.iter().skip(n/2) {
        chars[idx] = ')';
    }
    
    chars.into_iter().collect()
}

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