From: Shin-ichiro Hara <sinara@...>
Date: 1999-11-17T12:55:16+09:00
Subject: [ruby-list:18675] Re: rand

原です。

In message "[ruby-list:18668] rand"
    on 99/11/17, Ito Kazumitsu <ito@htk.hitachi-cable.co.jp> writes:
|
|伊藤と申します。

|は、次のようにしたほうが、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-1Ｃm  +  n-1Ｃm-1

で再帰させそうなのに、

  nＣm = (m/n) *  n-1Ｃm-1
       = (m-1)/n * n-1Ｃm-1  +  (1/n) * n-1Ｃm-1

の様なこの FAQ の方法は始めて見ました。

ただしこのサンプルはあくまで組合せ生成であり、順列はランダムにならないで
すよね。例えば sample(n, n) は [0, 1, ..., n-1] しか出てこない。だから、
「ランダムに選んだ配列」という表現はちょと誤解を招くのではないかと思いま
す。いっそ配列でなくハッシュにしてしまうとか。