logo标签列表

Objective-C中的非重复随机数

objective-crandom
7

我正在使用

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

但是每次我都会得到重复的结果。怎样才能填入选定的int数值范围中，以便程序循环时不会出现任何重复呢？

在C编程语言中，生成一个整数数组中的唯一随机数。 - outis
1
如果您不想要重复项，那么您并不是在寻找随机性http://en.wikipedia.org/wiki/Randomness，看起来您正在寻找一种随机洗牌算法http://en.wikipedia.org/wiki/Random_permutation。 - Maggie
谢谢Maggie，经过快速阅读有关洗牌的内容，我认为那就是我正在寻找的算法。 - Drahc
请参考以下链接：https://dev59.com/3nVC5IYBdhLWcg3wvT7g - Craig McQueen
6个回答
16

听起来你想要对一个集合进行洗牌，而不是"真正"的随机。只需创建一个数组，使所有位置与数字匹配，并初始化一个计数器：

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

其实我已经考虑到了内存处理的问题，特别是当我要随机生成200多个数字时。不过有一个问题，如果我要用这些数字来调用图片，该如何实现上述代码呢？NSString *ImageName = [NSString stringWithFormat :@"%d.png,i]; 谢谢。 - Drahc
哈哈，我还在担心内存消耗呢。感谢你的帮助，我在编程方面还很年轻。 - Drahc
没问题。希望在你能对我的工作造成任何威胁之前，我已经退休了 :-) - paxdiablo
哇，速度真快。谢谢 Pax，我稍后会试一下。再次感谢。 - Drahc
@Drahc，代码中有几个语法错误 - 我已经修复了它们，并提供了一个可以处理多个池的版本。 - paxdiablo
显示剩余2条评论
1

您可以使用格式保留加密来加密计数器。您的计数器只会从0开始递增，加密使用您选择的密钥将其转换为您想要的任何基数和宽度的似乎随机值。

块密码通常具有固定的块大小，例如64或128位。但是，格式保留加密允许您采用标准密码（如AES）并制作一个较小宽度的密码，其基数和宽度可以自行选择（例如基数2，宽度16），具有仍然具有加密强度的算法。

它保证永远不会发生碰撞（因为加密算法创建1：1映射）。它也是可逆的（双向映射），因此您可以将结果数字还原回您开始使用的计数器值。

AES-FFX是一种提议的标准方法来实现这一点。我已经尝试了一些基本的Python代码，它基于AES-FFX的想法，虽然不完全符合规范--在这里查看Python代码。它可以将计数器加密为一个看起来随机的7位十进制数或16位数字。

0
你需要跟踪你已经使用过的数字（例如，在数组中）。获取一个随机数，如果它已经被使用过，则将其丢弃。
2
洗牌是一种更高效的算法，符合要求：http://c-faq.com/lib/shuffle.html - outis
0

计算机不依赖于外部随机过程（如放射性衰变或用户输入），就会生成伪随机数 - 即具有许多随机数的统计特性，但是以序列重复。

这解释了通过洗牌来随机化计算机输出的建议。

丢弃以前使用过的数字可能会人为地延长序列，但代价是给出随机性印象的统计数据。

0

最好的方法是创建一个用于存储已使用数字的数组。在生成随机数后，将其添加到数组中。然后，在创建另一个随机数时，请确保它不在已使用数字的数组中。

0

除了使用辅助数组来存储已生成的随机数之外，在每次调用随机数生成函数之前调用随机数种子函数可能有助于在每次运行时生成不同的随机数序列。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接