C语言开发中如何缩减rand()随机数池实现不重复随机取值

你目前使用的「抽到已分配座位就重试」是最易实现的方案，但在座位占用率较高时会产生大量无效随机数生成，性能波动大。除该方案外，有两种成熟的稳定实现方案：

方案1：Fisher-Yates 洗牌法 #

这是无重复随机抽样场景的通用最优方案，核心逻辑是提前把所有可用座位打乱顺序，分配时直接按顺序取用，全程不会出现重复值，也不需要重试判断。
实现步骤：

• 将所有可用座位（对应你场景下前amount_rows/2排、每排amount_cols列的所有位置）映射为连续数组元素，每个元素存储座位的排、列号
• 从数组末尾向前遍历，每次生成一个[0, 当前遍历下标]范围内的随机数，将当前遍历位置的元素和随机下标位置的元素交换，完成全数组随机打乱
• 分配乘客座位时，按顺序从打乱后的数组中取出座位坐标赋值即可，所有取出的座位天然不重复

参考实现代码：

#include <stdlib.h>

typedef struct {
    int row;
    int col;
} Seat;

void assign_seats(int amount_rows, int amount_cols, Passenger passengers[amount_rows][amount_cols], int passenger_num) {
    int available_rows = amount_rows / 2;
    int total_available = available_rows * amount_cols;
    // 初始化可用座位池
    Seat* seat_pool = malloc(total_available * sizeof(Seat));
    int pool_idx = 0;
    for (int r = 0; r < available_rows; r++) {
        for (int c = 0; c < amount_cols; c++) {
            seat_pool[pool_idx].row = r;
            seat_pool[pool_idx].col = c;
            pool_idx++;
        }
    }

    // 执行Fisher-Yates洗牌
    for (int i = total_available - 1; i > 0; i--) {
        int rand_idx = rand() % (i + 1);
        Seat temp = seat_pool[i];
        seat_pool[i] = seat_pool[rand_idx];
        seat_pool[rand_idx] = temp;
    }

    // 直接按顺序分配，无重复
    for (int i = 0; i < passenger_num && i < total_available; i++) {
        int r = seat_pool[i].row;
        int c = seat_pool[i].col;
        passengers[r][c].in_row = 1;
    }

    free(seat_pool);
}

注意：你原有代码中rand() % amount_rows/2存在运算优先级问题，%和/优先级相同、按从左到右计算，实际执行逻辑是(rand() % amount_rows)/2，如果要实现对amount_rows/2取模，需要给除数加括号写成rand() % (amount_rows/2)。

方案2：动态剩余池抽样 #

这个方案不需要提前完成全量洗牌，适合不需要一次性分配完所有座位的场景：

• 同样先初始化存储所有可用座位的数组，维护一个变量记录当前剩余可用座位数，初始值为总可用座位数
• 每次需要分配座位时，生成[0, 当前剩余座位数-1]范围的随机下标，取出该下标的座位用于分配
• 将数组末尾的可用座位移动到刚才取出座位的下标位置，剩余可用座位数减1
• 重复上述过程直到完成所有分配，同样不会产生重复抽取，也没有无效重试

方案对比 #

• 重试法：代码量最少，不需要额外内存，但座位占用率超过70%后无效重试次数会快速上升，仅适合总座位数极少的场景
• 洗牌法：性能稳定，一次打乱后分配座位时间复杂度为O(1)，适合需要批量分配所有座位的模拟场景
• 动态剩余池：内存占用和洗牌法一致，支持动态按需分配，不需要提前完成全量打乱，灵活性更高

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