mjyさんのPython版と同じですが、i=0~19の範囲でループしつつ、その都度、選択される確率を求めて、採るか捨てるか決めていけばいいと思います。
i=0のとき、6/20の確率で選択します。i=0が選択されたとき、i=1が選択される確率は5/19になります。i=0が選択されなかったとき、i=1が選択される確率は6/19になります。この繰り返しです。
#include <stdio.h>
#include <stdint.h>
#ifdef _WIN32
#include <intrin.h>
#define rdtsc() __rdtsc()
#else
inline uint64_t rdtsc()
{
uint32_t hi, lo;
__asm__ __volatile__ ("rdtsc" : "=a"(lo), "=d"(hi));
return ((uint64_t)hi << 32) | (uint64_t)lo;
}
#endif
// [0..1]の乱数
double frand()
{
static uint64_t r = 123456789;
r = r * 0x0123456789abcdef + rdtsc();
return (double)r / UINT64_MAX;
}
int main()
{
int i;
int m = 20;
int n = 6;
for (i = 0; n > 0 && i < m; i++) {
if (frand() <= (double)n / (m - i)) {
printf("%d\n", i);
n--;
}
}
return 0;
}
乱数生成の関数は間に合わせで適当に作りましたので、精度とか信用しないでください。10万回くらい回して出現頻度を見てみましたが、概ね均一に分散していると思います。
補足
frand()
(適当に実装した乱数生成関数)ですが、CPUクロックカウンタ(rdtsc
命令)を利用している関係で、最初の1回目のfrand()
実行時のみ、結果の値が偏ります。2回目以降はまあまあ良い感じの乱数列を生成できます。上のコードのfor文の直前でfrand();
を1回実行しておくと、よりよい結果が得られます。