生成8位唯一随机数

Question

有没有更好的方法来生成8位唯一和随机号码在恒定时间？

以下实现返回8位唯一随机数，但复杂度为O（n = 256），因为它必须遍历is_generated []数组，直到它生成一个先前未生成的数组。另外它需要额外的空间is_generated。

uint8_t 
random_octate(void) 
{ 
    static bool  is_generated[256] = {false}; 
    uint32_t  num = rand()%256; 

    while(is_generated[num]) 
    { 
     num = rand() % 256; 
    } 

    is_generated[num] = true; 
    return num; 
} 

Answer 1

生成（0..255），然后洗牌。然后逐个发布元素。混洗是O（n），为256个值完成一次，因此每个元素的成本为O（1）;显然返回单个元素也是O（1）。

Answer 2

由于数据集是这样的限制不应该有在分配256个值的问题，他们洗牌并且为了提取它们，something like：

#include <stdio.h> 
#include <stdint.h> 
static uint8_t data[256]; 
static int index; 

void init_random() 
{ 
    srand(NULL); 

    index = 0; 
    for (int i = 0; i < 256; ++i) 
    data[i] = i; 

    // bad choice, use fisher-yates for example 
    for (int i = 0; i < 10000; ++i) 
    { 
    int i1 = rand()%256, i2 = rand()%256; 
    uint8_t t = data[i1]; 
    data[i1] = data[i2]; 
    data[i2] = t; 
    } 
} 

uint8_t extract() 
{ 
    return data[index++]; 
} 


int main(void) 
{ 
    init_random(); 
    for (int i = 0; i < 100; ++i) 
    printf("%d\n", extract()); 
}