[ruby-list:18668] rand

伊藤と申します。

rand のマニュアルに関して気付いたことですが、

日本語版マニュアルには

|rand(max)
|    0からmaxを越えない範囲の整数の乱数を発生します (maxは正の整数)． 

とあり、英語版には、

|rand(max)
|    Returns a random integer number greater than or equal to 0 and less
|    than the value of max. (max should be positive.) 

とありますが、これは当然英語版のほうが正しいですね。

さて、rand の仕様がそうなっているとすると、Ruby FAQ の

|7.3 0から51の中から重複のない5つをランダムに選ぶにはどうしますか
|
|次のメソッドは，0からnまでの数の中からm個をランダムに選んだ配列を返します．
|
|    def sample(n, m)
|      if m.zero?
|        []
|      else
|        s = sample(n-1, m-1)
|        t = rand(n+1)
|        s.concat s.include?(t) ? n : t
|      end
|    end

は、次のようにしたほうが、sample(n,m) が rand(n) の自然な拡張に
なって美しいと思います(単に好みの問題ですが)。

|7.3 0から51の中から重複のない5つをランダムに選ぶにはどうしますか
|
|次のメソッドは，0からn-1までのn個の数の中からm個をランダムに選んだ配列を
|返します．
|
|    def sample(n, m)
|      if m.zero?
|        []
|      else
|        s = sample(n-1, m-1)
|        t = rand(n)
|        s.concat s.include?(t) ? n-1 : t
|      end
|    end

しかし、なぜこのアルゴリズムが正しいのか疑問に思ったので、
次のようなプログラムを書いて検証してみました。

# 上のアルゴリズムで n個の数から m個の数を選ぶとき、
# n個の数それぞれが選ばれる確率の配列を求める。

    def sample_p(n, m)
      if m == 1
        a = [ (1.0/(n.to_f)) ]
        a *= n
      else
        a0 = sample_p(n-1, m-1)
        a = []

# i (0<=i<=n-2) が選ばれるのは、すでに選ばれているか、あるいは
# これまで選ばれておらずに今回 rand(n) で選ばれる場合である。

        (0..n-2).each{|i| a << (a0[i]+(1.0-a0[i])*(1.0/(n.to_f)))}

# n-1 が選ばれるのは、今回 rand(n) で選ばれるか、あるいは、
# すでに選ばれている i (0<=i<=n-2) が今回も選ばれる場合である。
 
        p = 1.0/(n.to_f)
        (0..n-2).each{|i| p += a0[i]*(1.0/(n.to_f)) }
        a << p
      end
    end

    p sample_p(20,8)
    p sample_p(100,13)

やってみると、もののみごとに、すべての確率は m/n となりますが、
それが一般に正しいことは、数学的帰納法で容易に証明できますね。
しかし、最初にアルゴリズムを考えた人は賢い。

********************
Ito Kazumitsu <[e-mail]>