既出の値を判定するコードについて思いついたこと(ビンゴゲームをネタに考える)
重複を許さないランダムな数値を一定数生成したいという機会は割りと遭遇する．このときの既出判定についてふと思いついたことを書き残す．
「そんなの一般的に使われている」というツッコミは置いておく．実装についての答えを示すものではなく，「簡単な用途であればこんな実装のほうが綺麗だな」って話．
きっかけ
去年開催された忘年会において，ビンゴゲームが開催された．その際に「白紙を渡すから，1-16の数字の中から，9個選んで3x3に適当に書け」ということになった．
自分で選ぶのも一興だが，時間がないときにはプログラムに任せて一瞬で作成してしまいたい．乱数を生成する事自体はAPIを使えば非常に簡単に生成できる．しかし，既出判定の部分が面倒臭いから簡単にできないものかと考えた．
以降のコードの目的は，ビンゴと同じ1-16の数値を被らないように9個選ぶこととする．変数や分岐などはC言語で考えている．
最初に思いつくやつ
出てきた数字を配列に格納し，生成した数字が出ているかを確認する．実装としては以下のような感じか．
int buf[9] = {0};
int i, j, t, c=0;
srand(time(NULL));
for (i=0; i<9; i++) {
while (1) { // 生成
t = rand() % 16 + 1;
for (j = 0; j < 9; j++) { // 既出チェック
if (buf[j] == t) c = 1;
}
if (c == 1) { c = 0; continue; } // c=1なら，既出でもう一回
break;
}
c = 0;
buf[i] = t;
// 出力処理
}
というように，どうにも入り組んだものになりがちである．他の処理があったりすると，読みたくないコードになってくる．既出判定のオーダーは，配列長nの半分程度だから，O(n/2)かな？
このコードだと取り扱う数字・個数が大きくなっても使えるが，毎回線形探索するのはオーバヘッドばかりかかる．かといって配列を毎回ソートし，二分探索みたいなことするのも複雑だ．ビンゴ生成にそこまでやるかという問いはさておき．
楽そうなコード(フラグ管理してみる, 配列)
フラグ管理してしまえば簡単だなと思った．乱数を添字にして，フラグ配列に1が入っていれば既出，0なら未出扱い．
int flag[16] = {0}; // フラグ管理
for (i=0; i<9; i++) {
tmp = rand() % 16 + 1; // 1-16の値をランダム生成
if (flag[i-1] == 1) continue; // 既出だから，もう一回
flag[i-1] = 1;
// 出力処理
}
大分スッキリした．既出判定は一回しか参照しないから，オーダーはO(1)のはず．問題は，取り扱う数値・個数が多くなったときに使用するメモリ量が大きくなりがちなこと．
もうちょい改良してみる．
楽そうなコード(フラグ管理してみる, 省メモリ)
フラグは0/1しかないのに，何もわざわざintの配列を確保する必要はない．変数一個だけでも行けるなと気づいた．ブール変数の配列とどっちがいいんだろうか．
unsigned int flag = 0; // 64ビットOSだと，変数の大きさは64ビット
int i, t;
srand(time(NULL));
for (i=0; i<9; i++) {
while (1) {
t = rand() % 16 + 1;
if ( (flag & (1 << (t-1) )) == 0 ) break; // t-1ビット目に1が立っていれば既出扱い，0なら未出
}
flag |= (1 << (t-1));
// 出力処理
}
初見だと少し読みにくい印象．
これもオーダ的にはO(1)か．64個までしか数字を取り扱わないのなら，これでも十分にできる．しかし，64以上の整数や個数を取扱いにくいのが難点．
多倍長的なものを実装するのが良いが，これは実装コストが一気に上がる(といっても配列のどの要素を見るかの処理を加えるくらいだが)．GMPを使えば楽にできそうだが，GMP使うと速度が下がりがちだから，要注意か．
完成版ビンゴジェネレータ
現実で使う機会が無さそうだから，ここでソースを挙げておく．
/* bingo.c */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main(void)
{
unsigned int flag = 0;
int i, t=0;
printf("=== Bingo Card Generator ===\n"
"================\n|");
srand(time(NULL));
for (i=0; i<9; i++) {
while (1) {
t = rand() % 16 + 1;
if ( (flag & (1 << (t-1) )) == 0 ) break;
}
flag |= (1 << (t-1));
if ( ((i % 3) == 0) && (i != 0) ) printf("\n|");
if (t >= 10) printf(" %d |", t);
else printf(" %d |", t);
}
printf("\n================\n");
printf("Good Luck!\n");
return 0;
}
/* E.O.F. */
$ gcc bingo.c -o bingo $ ./bingo === Bingo Card Generator === ================ | 2 | 16 | 8 | | 1 | 15 | 14 | | 13 | 5 | 4 | ================ Good Luck!
おわり
そこまで大きな数字・個数を取り扱わないものであれば，既出判定はフラグ管理するのがスッキリしててわかりやすそう．
