C语言生成1-16不重复随机数程序出现重复值是什么原因？

目标是实现C语言程序，生成1~16区间内的不重复随机数，要求每个数字恰好出现1次。实际运行时存在数字重复多次出现的异常，原实现代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main() {

    int x[16];
    int max = 16, min = 1;

    srand(time(NULL));

    for (int i = 0; i < 16; i++) {

        x[i]= (rand() % (max-min+1)) + min;

        for (int j = 0; j < i; j++) {

            if (x[i] == x[j]) {

                while (x[i] == x[j]) {
                            
                    x[i] = (rand() % (max-min+1)) + min;
                }
            }
        }
    }

    for (int i = 0; i < 16; i++) {

        printf("\n%d", x[i]);
    }

    return 0;
}

原代码的核心问题出在内层去重逻辑的设计漏洞：

• 当检测到当前位置i的随机数和位置j的已存数字重复时，while循环仅保证新生成的数字不等于当前j位置的值，没有校验新值是否会和0~j-1位置的其他已存数字重复。
• 内层j的遍历是从0到i-1单向执行的，重新生成随机数后不会回溯重新检查更早位置的元素，很容易出现新值和更早位置元素重复但未被检测到的情况。

实际触发场景示例：当i=3时，已存入数组的元素为x[0]=3, x[1]=7, x[2]=12，第一次生成x[3]=7，触发j=1位置的重复判断，进入while循环重新生成随机数。如果新生成的值是3，此时while判断x[i] != x[j]（7）就会直接退出循环，但3已经和x[0]的值重复，后续j遍历到0位置时不会再对这个新生成的3做校验，最终数组里就会出现重复的3。

两种常见的正确实现方式：

方案1：校验通过才存入 #

每次生成随机数后，遍历所有已存入的元素检查重复，只要发现重复就重新生成，直到确认新数和所有已存数都不重复再存入数组，修正后的核心逻辑如下：

for (int i = 0; i < 16; i++) {
    int num;
    int is_dup;
    do {
        is_dup = 0;
        num = (rand() % (max - min + 1)) + min;
        for (int j = 0; j < i; j++) {
            if (x[j] == num) {
                is_dup = 1;
                break;
            }
        }
    } while (is_dup);
    x[i] = num;
}

方案2：Fisher-Yates 洗牌算法（效率更高） #

先初始化1~16的顺序数组，再从后往前遍历数组，每次将当前位置元素和随机位置的元素交换，最终得到的数组就是打乱的不重复序列，时间复杂度更低，不存在反复生成随机数重试的开销：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main() {
    int x[16];
    int min = 1;
    srand(time(NULL));

    // 初始化顺序数组
    for (int i = 0; i < 16; i++) {
        x[i] = min + i;
    }

    // 洗牌打乱
    for (int i = 15; i > 0; i--) {
        int j = rand() % (i + 1);
        // 交换i和j位置的元素
        int temp = x[i];
        x[i] = x[j];
        x[j] = temp;
    }

    for (int i = 0; i < 16; i++) {
        printf("%d\n", x[i]);
    }
    return 0;
}

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