非重复的随机数

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

Answer 2

你需要跟踪你已经使用的数字（例如，在一个数组中）。获取一个随机数字，如果它已被使用，则丢弃它。

Answer 3

不依赖外部随机过程，如放射性衰变或用户输入，计算机将始终生成伪随机数 - 即具有许多随机数的统计特性的数字，但在序列中重复。

这就解释了对随机通过混洗输出的建议。

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

Answer 4

做到这一点的最好方法是为已经使用的数字创建一个数组。在创建了一个随机数之后，将其添加到数组中。然后，当您创建另一个随机数时，请确保它不在所使用数字的数组中。

Answer 5

除了使用辅助数组来存储已经生成的随机数，调用随机数。在每次随机号码呼叫之前播种功能。生成函数可能有助于生成不同的seq。在每次运行中随机数字。

Answer 6

你可以使用Format-Preserving Encryption加密的计数器。你的计数器只是从0开始，并且加密使用你选择的一个键将它变成一个看似随机的任意基数和宽度的随机值。

分组密码通常具有固定的块大小，例如， 64或128位。但格式保留加密允许您采用AES之类的标准密码，并使用仍然具有密码稳健性的算法制作您希望的任何基数和宽度（例如基数2，宽度16）的较小宽度密码。

它是保证不会有碰撞（因为加密算法创建一个1：1映射）。它也是可逆的（一种双向映射），所以你可以把结果编号并返回到你开始的计数器值。

AES-FFX是一个被提议的标准的方法来实现这一点。我已经尝试了一些基于AES-FFX思想的基本Python代码，尽管不完全符合 - see Python code here。它可以例如将计数器加密为随机的7位十进制数或16位数。