如何讓我的C程序隨機選擇

Question

我想打一個C程序，隨機選擇號碼6個號碼的範圍1 - 37，無需重複任何先前排列。例如，假設程序隨機選擇1,2,3,4,5,6。如果隨機選擇下一個排列爲2,1,3,4,5,6，則表示沒問題。但是，如果再次選擇1,2,3,4,5,6，則表示不正常。我希望這樣繼續下去，直到沒有更多的可用集合可用。我將如何去編寫這個C程序？

Answer 1

現在貼在下面的KNUTH洗牌的答案也相當考究。但是它不符合OP在他的問題中提出的特殊要求。

的OP說，他希望能夠以隨機順序選擇所有集合，直到他的計劃已經消耗了他們。所以在這裏。出於演示的目的，我們將理解「選擇」表示「打印」。

的可能集合的「在1-37的範圍內6個獨特的數字」的總數可以表示爲：

TOTAL_NUMBER_OF_SETS = 37*36*35*34*33*32 = 1673844480 

1673844480（1.6十億）一個帶符號的32位的數字內配合很好。並且每一個獨特的集合可能被分配一個唯一的整數ID。

所以......如果你能生成之間[0,1673844479]一個隨機數，我們可以映射到一個非常具體的6個獨特的整數。

要構建一套，我們需要一個輔助功能，這將允許我們跟蹤它的過程中構建集的迭代過程中已經使用1-37之間的值。這時，一個小模運算數學來幫助它的設置的6位數我們映射一個ID號：

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

const uint32_t TOTAL_NUMBER_OF_SETS = 37*36*35*34*33*32; // = 1673844480 

// returns the Nth value value from the ordered set {1,range}, 
// skipping over elements previous selected 
int GetAvailableElementFromSet(int n, int range, int inuse[]) 
{ 
    int i = 0, x; 
    for (x = 0; x < range; x++) 
    { 
     if (inuse[x] == 0) 
     { 
      if (i == n) 
      { 
       inuse[x] = 1; 
       return x + 1; // +1 since the loop variable has a zero-based index 
      } 
      i++; 
     } 
    } 
    return -1; // error 
} 


void GetSpecificSet(uint32_t setindex, int output[]) 
{ 
    int index; 
    int inuse[37] = {}; // boolean array of elements already picked for the output set. zero-init to all false 
    int j,k; 

    if (setindex >= TOTAL_NUMBER_OF_SETS) 
     return; // error! 

    for (j = 0; j < 6; j++) 
    { 
     index = setindex % (37-j); 
     output[j] = GetAvailableElementFromSet(index, 37, inuse); 
     setindex = setindex/(37-j) ; 
    } 
} 

而只是爲了證明這個作品，我們可以有另一種功能迭代所有集：

void PrintSet(uint32_t setindex) 
{ 
    int output[6]; 
    GetSpecificSet(setindex, output); 
    printf("%d, %d, %d, %d, %d, %d\n", output[0], output[1], output[2], output[3], output[4], output[5]); 
} 

void PrintAllSetsInOrder() 
{ 
    uint32_t index; 
    for (index = 0; index < TOTAL_NUMBER_OF_SETS; index++) 
    { 
     PrintSet(index); 
    } 
} 

現在上面的程序將打印出所有的設置從開始：

{1,2,3,4,5,6} // first set 
{2,1,3,4,5,6} // second set 
{3,1,2,4,5,6} // third set 

而且隨着

結束

然後明明打印一組隨機：

void PrintRandomSet() 
{ 
    PrintSet(rand() % TOTAL_NUMBER_OF_SETS); 
} 

但OP想要打印的隨機順序重複沒有所有集合。這變得棘手，因爲我們必須跟蹤先前生成的隨機數值。我可以想到幾種方法來做到這一點。最明顯的候選解決方案是保持由TOTAL_NUMBER_OF_SETS位組成的位掩碼。那就是：

#define IS_BIT_SET(bmask, bitindex) (bmask[bitindex/8] & (0x01<<(bitindex%8))) 
#define SET_BIT(bmask, bitindex) {bmask[bitindex/8] |= (0x01<<(bitindex%8));} 
uint8_t* bitmask = calloc(TOTAL_NUMBER_OF_SETS/8 + 1); 

這是大約200MB的內存分配。大，但可行。然後，我們繼續從範圍[0-TOTAL_NUMBER_OF_SETS]中選取隨機數，檢查位掩碼是否已被使用，然後在設置位掩碼位置後使用隨機數調用PrintSet。重複，直到打印完所有TOTAL_NUMBER_OF_SETS。

僞的工作問題的解決方案

for (x = 0; x < TOTAL_NUMBER_OF_SETS; x++) 
{ 
    index = rand()%TOTAL_NUMBER_OF_SETS; 
    while (IS_BIT_SET(bitmask, index)) 
    { 
     index = (index + 1) % TOTAL_NUMBER_OF_SETS; 
    } 
    SET_BIT(bitmask, index); 
    PrintSet(index); 
} 

代碼，但現在，這應該只是罰款。但隨着位掩碼陣列開始填滿，它會變得很慢。後面的迭代將花費大部分時間來掃描尋找未設置索引值的位數組。關於如何對大集合進行高效和統一的排列，還有其他關於StackOverflow的討論。也許數據庫是有保證的。去尋找這些解決方案，並將其應用於此獲勝。

Answer 2

使用Knuth Shuffle。給你O（n）漸近的複雜性。

#include <stdlib.h> 
#include <string.h> 

int rrand(int m) 
{ 
    return (int)((double)m * (rand()/(RAND_MAX+1.0))); 
} 

#define BYTE(X) ((unsigned char *)(X)) 
void shuffle(void *obj, size_t nmemb, size_t size) 
{ 
    void *temp = malloc(size); 
    size_t n = nmemb; 
    while (n > 1) { 
    size_t k = rrand(n--); 
    memcpy(temp, BYTE(obj) + n*size, size); 
    memcpy(BYTE(obj) + n*size, BYTE(obj) + k*size, size); 
    memcpy(BYTE(obj) + k*size, temp, size); 
    } 
    free(temp); 
} 

編號：http://rosettacode.org/wiki/Knuth_shuffle#C