C++中如何让rand函数生成不重复随机数实现待办任务单次抽取

你遇到的重复抽取问题本质不是rand()生成重复值，而是没有对已抽取的任务做排除逻辑，即使随机数完全不重复，两次随机到相同数组下标依然会拿到重复任务，以下是三种可落地的实现方案：

方案1：Fisher-Yates 洗牌法（最推荐） #

这是实现无重复随机抽取的最优方案，时间复杂度O(n)，不需要额外空间，也不会产生重复问题。逻辑是提前把整个任务列表打乱顺序，之后按顺序逐个取元素即可，天然保证每个任务只取一次。

#include <vector>
#include <algorithm>
#include <random>

// 初始化任务列表
std::vector<std::string> tasks = {"任务1", "任务2", "任务3", "任务4"};
// 初始化随机数生成器
std::random_device rd;
std::mt19937 g(rd());
// 打乱整个数组顺序
std::shuffle(tasks.begin(), tasks.end(), g);

// 之后每次按顺序取元素即可，用指针记录当前取到的位置
int current_idx = 0;
// 抽取逻辑
if (current_idx < tasks.size()) {
    std::string selected_task = tasks[current_idx];
    current_idx++;
    // 处理抽到的任务
}

• 实现简单，不需要额外维护标记集合
• 性能最优，仅需要一次打乱操作，后续抽取都是O(1)复杂度
• 完全避免重复抽取的可能

方案2：标记已抽取元素（适合需要保留原数组顺序的场景） #

如果不能修改原任务列表的顺序，可以额外维护一个布尔数组或者集合，记录已经抽到过的下标，每次随机到下标之后先判断是否已经被抽取过，如果是就重新随机，直到抽到未抽取的下标。

#include <vector>
#include <cstdlib>
#include <ctime>

std::vector<std::string> tasks = {"任务1", "任务2", "任务3", "任务4"};
std::vector<bool> used(tasks.size(), false);
int remain_count = tasks.size();
// 初始化随机种子，注意rand()只需要初始化一次
std::srand(std::time(nullptr));

// 抽取逻辑
if (remain_count > 0) {
    int idx;
    do {
        idx = std::rand() % tasks.size();
    } while (used[idx]);
    used[idx] = true;
    remain_count--;
    std::string selected_task = tasks[idx];
    // 处理抽到的任务
}

• 原任务列表顺序完全不会被修改
• 逻辑容易理解
• 缺点：剩余任务很少时，可能需要多次循环才能抽到未使用的下标，性能会下降

方案3：抽取后删除元素（适合允许修改原数组的场景） #

每次随机抽到任务之后，直接把该任务从原vector中移除，后续随机只会在剩余的任务中抽取，天然不会重复。

#include <vector>
#include <cstdlib>
#include <ctime>

std::vector<std::string> tasks = {"任务1", "任务2", "任务3", "任务4"};
std::srand(std::time(nullptr));

// 抽取逻辑
if (!tasks.empty()) {
    int idx = std::rand() % tasks.size();
    std::string selected_task = tasks[idx];
    // 移除已经抽到的任务
    tasks.erase(tasks.begin() + idx);
    // 处理抽到的任务
}

• 不需要额外维护标记或者指针
• 逻辑直观
• 缺点：vector的erase操作是O(n)复杂度，任务量很大时性能不如洗牌法，且原任务列表会被修改，无法保留原始数据

注意：如果使用rand()函数，务必只在程序启动时调用一次srand()初始化随机种子，多次初始化反而会导致生成的随机数重复。如果对随机性要求更高，更推荐使用C++11引入的<random>库中的随机数生成器替换rand()。

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