ナンプレ(数独)問題作成プログラム その14 疑似乱数
疑似乱数
これから digging hole アルゴリズムでナンプレの問題を作りたいわけだが、そのために疑似乱数を使う。だいたい何でもいいんだけど、比較的新しい(のでお気に入りの)xsadd を使ってみる。小さいし、速いし、MITライセンスだし。
元のソースはXORSHIFT-ADD (XSadd)
にある。
ナンプレで使いそうな疑似乱数関係関数をcommon.cに追加する。また今回は状態空間をグローバルに置く。
xsadd_t xsadd;
あとは関数
/** * 0 から n (含まない) までの数をランダムに生成する * @param n 範囲 * @return 0 から n(含まない)までの数を返す */ int get_random(unsigned int n) { return n * xsadd_float(&xsadd); } /** * ナンプレで使う数字をランダムに生成する * @param symbols ナンプレで使う数字が重複なくランダムな順番でセットされる */ void get_random_symbol(uint16_t symbols[LINE_SIZE]) { uint16_t mask = 1; for (int i = 0; i < LINE_SIZE; i++) { symbols[i] = mask; mask = mask << 1; } for (int i = 0; i < LINE_SIZE; i++) { int r = get_random(LINE_SIZE); uint16_t tmp = symbols[i]; symbols[i] = symbols[r]; symbols[r] = tmp; } } /** * 0 から LINE_SIZE -1までの数をランダムに生成する。 * @param numbers 0 からLINE_SIZE -1 までの数が重複なくセットされる。 */ void get_random_number(uint16_t numbers[LINE_SIZE]) { get_random_number_size(numbers, LINE_SIZE); } /** * 0 から size -1までの数をランダムに生成する。 * @param numbers 0 からsize -1 までの数が重複なくセットされる。 * @param size numbers 配列の大きさ */ void get_random_number_size(uint16_t numbers[], int size) { for (int i = 0; i < size; i++) { numbers[i] = i; } for (int i = 0; i < size; i++) { int r = get_random(size); uint16_t tmp = numbers[i]; numbers[i] = numbers[r]; numbers[r] = tmp; } } /** * 0 から size - 1までの数をランダムに生成する。 * get_random_number_size と同じだが配列の型が違う * @param numbers 0 からsize -1 までの数が重複なくセットされる。 * @param size numbers 配列の大きさ */ void shuffle_int(int array[], int size) { for (int i = 0; i < size; i++) { int r = get_random(size); int tmp = array[i]; array[i] = array[r]; array[r] = tmp; } }
同じような関数がいくつもあって美しくないが、使いやすいということで勘弁。
短いけどこんなもんで。
疑似乱数といえば旧約聖書と言われるコレ
疑似乱数生成器をちょいちょいと作って、卒論や修論にしようと考える情報系の学生ならこれは必読ですよ。凶器にもなるし。
- 作者: Donald E.Knuth,有沢誠,和田英一,斎藤博昭,長尾高弘,松井祥悟,松井孝雄,山内斉
- 出版社/メーカー: アスキー
- 発売日: 2004/10
- メディア: 単行本
- 購入: 1人 クリック: 80回
- この商品を含むブログ (44件) を見る
MSaito/MTToolBox · GitHub
MTToolBox: メインページ