C++でrand7()を使ってrand10()を実装する方法【棄却サンプリング】

問題概要

1から7までの一様なランダム整数を生成する関数 rand7() が与えられているとします。この関数を利用して、1から10までの一様なランダム整数を生成する関数 rand10() を実装するのが本記事の目的です。なお、乱数を直接生成するライブラリ関数を新たに使用することはできません。

解法のポイント:棄却サンプリング

この問題を解く鍵は、rand7() を2回呼び出すことで、より広い範囲の一様分布を作り出すことです。

次の式を考えてみましょう。

rand40 = (rand7() - 1) * 7 + (rand7() - 1)

これは7進法の2桁の数とみなすことができ、0から48までの49個の整数が等確率で得られます。しかし、49個の値を10通りに均等に振り分けることはできないため、ここで「棄却(リジェクト)」の考え方を使います。

具体的には、40以上の値が生成された場合は採用せず、再度生成し直します。こうすることで0から39までの40個の値だけが残り、それぞれが等しい確率で出現します。最後に % 10 + 1 を適用すれば、1から10の各数値がちょうど4回ずつ対応するため、完全に一様なランダム整数が得られるのです。

アルゴリズムの手順

• 変数 rand40 を 40 で初期化する
• rand40 >= 40 の間、次の処理を繰り返す:
  • rand40 := (rand7() - 1) * 7 + (rand7() - 1)
• rand40 % 10 + 1 を返す

C++による実装例

それでは、実際のコードを見ていきましょう。

#include <bits/stdc++.h>
using namespace std;
int rand7(){
   return 1 + rand() % 7;
}
class Solution {
   public:
   int rand10() {
      int rand40 = 40;
      while(rand40 >= 40){
         rand40 = (rand7() - 1) * 7 + (rand7() - 1);
      }
      return rand40 % 10 + 1;
   }
};
main(){
   srand(time(NULL));
   Solution ob;
   cout << (ob.rand10()) << endl;
   cout << (ob.rand10()) << endl;
   cout << (ob.rand10()) << endl;
}

入力

関数を3回呼び出す

出力

2
2
6

計算量の評価

1回のループで値が受理される確率は 40/49 であるため、rand7() の期待呼び出し回数は 2 × 49/40 ≒ 約2.45回です。棄却が続く確率は指数的に減少するため、時間計算量は期待値 O(1)、空間計算量も O(1) で非常に効率的な実装と言えます。