生成k个小于n的互不相同的随机数

「来源」

《编程珠玑》习题1.4：如果认真考虑了习题3，你将会面对生成小于n且没有重复的k个整数的问题。最简单的方法就是使用前k个正整数。这个极端的数据集合将不会明显的改变位图方法的运行时间，但是可能会歪曲系统排序的运行时间。如何生成位于0至n - 1之间的k个不同的随机顺序的随机整数？尽量使你的程序简短高效。

「基本思想」

基本思想：   

1. 获得小于n的随机数可以使用rand()%n获得，但既然是伪随机的，当然有可能重复； 

2. 利用洗牌的原理，将n个数(0至n-1)按次序排好，依次让每个数和一个随机挑选出的位子进行互换，这样肯定不会重复，而且次序被打乱，具有随机性。 只用交换k次，就可以取出k个小于n的互不相同的随机数。

「具体实现」windows下（vc6.0, C语言）

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

#define N 20
#define K 10

void swap(int *a, int *b)
{
    *a ^= *b;
    *b ^= *a;
    *a ^= *b;
}

/******************************************************************************
*函数名称：void generateDiffRandV1(int a[], int n)
*函数功能：产生互不相同的随机数
*入口参数：
*返 回 值：无
*备 注：以空间换时间
*******************************************************************************/
void generateDiffRandV1(int a[], int n, int k)
{
    int i;
    time_t t;

    for (i = 0; i < n; i++){
        a[i] = i;
    }

    srand((int)time(&t));
    for (i = 0; i < k; i++){
        swap(&a[i], &a[i+rand()%(n-i)]);
    }
}

/******************************************************************************
*函数名称：void generateDiffRandV2(int a[], int n)
*函数功能：产生互不相同的随机数(产生随机数的范围是1~n-1)
*入口参数：
*返 回 值：无
*
*思 路：先生成一个放置座号的数组，然后从中随机抽取，抽取后为防止重复，立即归零。
* ：每次生成座号，只需判断是否为0 即可，大大提高了程序执行的效率。
*******************************************************************************/
void generateDiffRandV2(int a[], int n)
{
    int *flag =(int *)malloc(sizeof(int) * n);
    static flag_once = 0;
    int i, index;
    
    for(i = 0; i < n; i++) flag[i] = i+1;
    if(!flag_once){
        srand(time(0));
        flag_once = 1;
    }
    
    for(i = 0; i < n;){
        index = rand() % n;
        if(flag[index] != 0){
            a[i++] = flag[index]-1;
            flag[index] = 0;
        }
    }
    free(flag);
}

void printArray(int a[], int n)
{
    int i;

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

int main()
{
    int a[N];
    generateDiffRandV1(a, N, K);
    printArray(a, K);
    
    generateDiffRandV2(a, N);
    printArray(a, N);
    
    return 0;
}

「出错」

为什么generateDiffRandV1()函数生成的随机数当中会有同时出现多个'0'？

问题解决了,swap函数不对，修正如下：

void swap(int *a, int *b)
{
    if (a != b){
        *a ^= *b;
        *b ^= *a;
        *a ^= *b;
    }
}

讨论见地址