编程小技巧

        今天跟大家分享的小技巧是关于生成无重复随机数的。在《随机函数原理》中我们已经讲述了随机数的生成问题，接下来我们来谈一谈如何生成N个不重复的随机数。

        我们要解决两个问题：

1. 生成N个随机数。
2. 所有的随机数不重复。

        通过思考我们知道，生成N个随机数比较简单，我们只需要循环执行随机数函数N次即可。但是第二个问题有一些难度，如何让这N个随机数不重复呢？我们先提出一个不太高效的算法：

每当生成一个随机后，我们将这个数与已生成的随机数组中的元素做比较，判断已生成数组中是否已经存在了这个数，如果不存在，则插入数组中，否则放弃此随机数，再生成一个新的随机数。

        这是很多朋友容易想到的办法，粗略来看这个算法还是可行的，如果N==10或N < 100问题不大，随机数出现重复的可能比较小，但如果N非常大，比如一千或一万，那么每次生成随机数之后与已生成数组中元素比较的过程就非常耗时，加上重复的机率增加，为了生成一千个不重复的随机数，你的程序可能会执行几千次甚至几万次随机函数才能找到这一千个不重复的随机数。

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h> 
#define N (10)
int array_have(int* array, int rnd, int len)
{
        for (int i = 0; i < len; i++)
        {
                if (array[i] == rnd)
                {
                        return 1;
                }
        }
        return 0;
}
int main(int argc, char* args[])
{
        srand((int)time(0));
        int array[N];
        int len   = 0;
        int times = 0;
        for (; len < N; times++)
        {
                int rnd = rand() % N;
                if (!array_have(array, rnd, len))
                {
                        array[len++] = rnd;
                }
        }
        for (int i = 0; i < N; i++)
        {
                printf("%3d ", array[i]);
        }
        printf("\ntimes %d\n", times);

        return 0;
}

        经过测试，生成无重复随机数：

• N==10          执行了 46次
• N==100        执行了 341次
• N==1000      执行了 3972次
• N==10000    执行了 65846次

        可见，当N的值很大的时候程序执行的效率就低。那么有没有什么更好的办法呢？我们的目标是想生成N个无重复的随机数，我们可以转换一下思想，假设我们有N个无重复的顺序排列的数组，我们只需要将它们的排列顺序随机打乱即可。比如我们用0～9来举例，假设我们已经有了10个无重复的数组array，它们是顺序排列的：

0, 1, 2, 3, 4, 5, 6, 7, 8, 9

        我们生成一个0～9的随机数rnd，假设是rnd == 7，于是我们将array数组中下标为7的数，与数组的最后一个位置的数交换位置：

0, 1, 2, 3, 4, 5, 6, 9, 8, 7

                             ^      ^ 

        接下来再生成一个0～8的随机数，假设rnd == 2，于是我们再将array数组中下标为2的数，与数组中倒数第二个位置的数交换位置：

0, 1, 8, 3, 4, 5, 6, 9, 2, 7

    ^                      ^

        接下来再生成一个0～7的随机数，假设rnd ==5，于是我们再将array数组中下标为5的数，与数组中倒数第三个位置的数交换位置：

0, 1, 8, 3, 4, 9, 6, 5, 2, 7

            ^       ^

        这样重复执行10次就可以得到10个无重复的随机数，而我们的算法只执行了10次。我们来看一下程序：

#include <math.h> 
#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 
#define N (100)
int main(int argc, char* args[])
{
        srand((int)time(0));
        int array[N];
        //生成N个顺序排列的数
        for (int i = 0; i < N; i++)
        {
                array[i] = i;
        }
        //随机算法
        for (int i = 0; i < N; i++)
        {
                //生成随机数，做为数组的下标
                int rnd          = rand() % (N - i); 
                //将随机下标与数组最后一个（每执行一次，等待排列的数组大小减一）元素交换位置
                int temp         = array[rnd];
                array[rnd]       = array[N - i - 1]; 
                array[N - i - 1] = temp;
        }
        //显示结果
        for (int i = 0; i < N; i++)
        {
                printf("%3d ", array[i]);
        }
        printf("\n");
        return 0;
}

        请大家仔细分析上面程序，它的巧妙在于不直接生成随机数，生成N个随机数做为这个数组的下标：

1. 生成N个连续的数放入数组
2. 生成N个随机数做这个数组的下标
3. 每生成一个随机数下标，待生成随机数的范围减一
4. 将这个随机下标与随机数范围末尾的元素互换

        这个算法非常高效，它整个过程只需要两次循环，即初始化一个连续的数组和生成随机数组。实际上这个算法是先生成N个顺序的排列的数，然后再随机将其顺序打乱。

        今天的小技巧你学会了吗？