以下是Fisher-Yates的C实现,我想使用一个甲板洗牌程序.我正在做这个(n =数组的长度)？
注意：do-while循环尝试纠正模偏(见here).它为该过程增加了一些开销,如果不关心低位偏差,可以消除该过程.
void shuffle(int *array,int n) {
int i,j,tmp,upper_bound;
srand(time(NULL));
for (i = n - 1; i > 0; i--) {
upper_bound = RAND_MAX - ((RAND_MAX % (i + 1)) + 1);
do {
j = rand() % (i + 1);
} while (j > upper_bound);
tmp = array[j];
array[j] = array[i];
array[i] = tmp;
}
}
解决方法
首先,您应该提取用于生成在0(包括)和n(独占)之间均等分配到一个单独的函数的随机数的代码.这也是您在其他地方需要工作的一项不错的工作.
第二,我不会在洗牌功能中调用srand,而是依赖于调用者初始化随机数生成器.这样你可以在一秒钟内洗牌一次以上.
第三,你应该做j>的测试. upper_bound除以i 1.我不大可能会接近RAND_MAX.
static int rand_int(int n) {
int limit = RAND_MAX - RAND_MAX % n;
int rnd;
do {
rnd = rand();
} while (rnd >= limit);
return rnd % n;
}
void shuffle(int *array,int n) {
int i,tmp;
for (i = n - 1; i > 0; i--) {
j = rand_int(i + 1);
tmp = array[j];
array[j] = array[i];
array[i] = tmp;
}
}
要检查此实现是否正确,您需要确保随机数生成器询问log2(n！)位的随机性.换句话说,给予rand_int函数的所有ns的乘积必须是n！