原です。

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

私もこの仕様に賛成です。サンプルではあるけれど。

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

私も最初見た時不思議でした。普通この手のアルゴリズムは、

  nCm = n-1Cm  +  n-1Cm-1

で再帰させそうなのに、

  nCm = (m/n) *  n-1Cm-1
       = (m-1)/n * n-1Cm-1  +  (1/n) * n-1Cm-1

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

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