objective-c - 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.

这将从一个不断减少的池中返回一个随机值，保证不会重复。当然，您必须提防池大小降至零，并智能地重新初始化池。

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

像这样使用静态值的 C 函数应该可以解决问题。调用它

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() 函数。这允许每个客户端(代码中的位置)拥有自己的自动分配和释放的池，但如果您愿意，您仍然可以共享池。