非重複的隨機數

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位數。