Objective-C中的非重复随机数

Question

我正在使用

for (int i = 1, i<100, i++)
    int i = arc4random() % array count;

但我每次都会重复.如何int从范围中填写所选的值,以便在程序循环时我不会得到任何欺骗？

Answer 1

听起来你想要改组而不是"真正的"随机性.只需创建一个数组,其中所有位置都与数字匹配并初始化计数器:

num[ 0] =  0
num[ 1] =  1
: :
num[99] = 99
numNums = 100

然后,只要您想要一个随机数,请使用以下方法:

idx = rnd (numNums);       // return value 0 through numNums-1
val = num[idx];            // get then number at that position.
num[idx] = val[numNums-1]; // remove it from pool by overwriting with highest
numNums--;                 //   and removing the highest position from pool.
return val;                // give it back to caller.

这将从不断减少的池中返回一个随机值,保证不重复.当然,您必须小心将池运行到零大小,并智能地重新初始化池.

这是一个更确定的解决方案,而不是保留已使用数字的列表并继续循环,直到找到不在该列表中的数字.随着池变小,这种算法的性能会降低.

使用这样的静态值的AC函数应该可以解决问题.叫它

int i = myRandom (200);

设置池(任何数字为零或更大,指定大小)或

int i = myRandom (-1);

从池中获取下一个数字(任何负数就足够了).如果函数无法分配足够的内存,则返回-2.如果池中没有剩余数字,它将返回-1(此时您可以根据需要重新初始化池).这是一个单元测试主要功能供您试用:

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

#define ERR_NO_NUM -1
#define ERR_NO_MEM -2

int myRandom (int size) {
    int i, n;
    static int numNums = 0;
    static int *numArr = NULL;

    // Initialize with a specific size.

    if (size >= 0) {
        if (numArr != NULL)
            free (numArr);
        if ((numArr = malloc (sizeof(int) * size)) == NULL)
            return ERR_NO_MEM;
        for (i = 0; i  < size; i++)
            numArr[i] = i;
        numNums = size;
    }

    // Error if no numbers left in pool.

    if (numNums == 0)
       return ERR_NO_NUM;

    // Get random number from pool and remove it (rnd in this
    //   case returns a number between 0 and numNums-1 inclusive).

    n = rand() % numNums;
    i = numArr[n];
    numArr[n] = numArr[numNums-1];
    numNums--;
    if (numNums == 0) {
        free (numArr);
        numArr = 0;
    }

    return i;
}

int main (void) {
    int i;

    srand (time (NULL));
    i = myRandom (20);
    while (i >= 0) {
        printf ("Number = %3d\n", i);
        i = myRandom (-1);
    }
    printf ("Final  = %3d\n", i);
    return 0;
}

这是一次运行的输出:

Number =  19
Number =  10
Number =   2
Number =  15
Number =   0
Number =   6
Number =   1
Number =   3
Number =  17
Number =  14
Number =  12
Number =  18
Number =   4
Number =   9
Number =   7
Number =   8
Number =  16
Number =   5
Number =  11
Number =  13
Final  =  -1

请记住,因为它使用静态,如果他们想要维护自己独立的池,则从两个不同的地方调用是不安全的.如果是这种情况,静态将被替换为"属于"调用者的缓冲区(保持计数和池)(为此目的可以传入双指针).

而且,如果您正在寻找"多池"版本,我将其包含在此处以保证完整性.

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

#define ERR_NO_NUM -1
#define ERR_NO_MEM -2

int myRandom (int size, int *ppPool[]) {
    int i, n;

    // Initialize with a specific size.

    if (size >= 0) {
        if (*ppPool != NULL)
            free (*ppPool);
        if ((*ppPool = malloc (sizeof(int) * (size + 1))) == NULL)
            return ERR_NO_MEM;
        (*ppPool)[0] = size;
        for (i = 0; i  < size; i++) {
            (*ppPool)[i+1] = i;
        }
    }

    // Error if no numbers left in pool.

    if (*ppPool == NULL)
       return ERR_NO_NUM;

    // Get random number from pool and remove it (rnd in this
    //   case returns a number between 0 and numNums-1 inclusive).

    n = rand() % (*ppPool)[0];
    i = (*ppPool)[n+1];
    (*ppPool)[n+1] = (*ppPool)[(*ppPool)[0]];
    (*ppPool)[0]--;
    if ((*ppPool)[0] == 0) {
        free (*ppPool);
        *ppPool = NULL;
    }

    return i;
}

int main (void) {
    int i;
    int *pPool;

    srand (time (NULL));
    pPool = NULL;
    i = myRandom (20, &pPool);
    while (i >= 0) {
        printf ("Number = %3d\n", i);
        i = myRandom (-1, &pPool);
    }
    printf ("Final  = %3d\n", i);
    return 0;
}

从修改后的内容可以看出main(),首先需要初始化int指针NULL然后将其地址传递给myRandom()函数.这允许每个客户端(代码中的位置)拥有自己的池,该池自动分配和释放,但如果您愿意,仍然可以共享池.