ランダム集合とランダム順列 |
作成日：1999-10-04 最終更新日： |
たとえば、１からnまでの整数を、 m 個ランダムに選ぶ(集合として選ぶので順番は問わない)にはどうすればいいか。 無作為抽出に使えるこの問にはいろいろな解法がある。 乱数発生の回数が m 回で抑えられるスマートな方法が、 J.L.ベントリーの「プログラマのうちあけ話」 に出ている。 awk で書かれたサンプルの一部を掲げる。
for (j = n-m+1; j <= n; j++) {
t = 1 + int(j * rand())
if (t in s) s[j] = 1
else s[t] = 1
}
for (i in s) print i
これを Javascript 用に書き直した。n > m > 0 で、n, m はどちらも整数である。 書き直すといっても、ほとんど同じだ。ここで、配列sは、連想配列のような使い方をしている。
上の問題で、 順番も含めて m 個ランダムに並べる場合はどうか。 スマートな方法が、 同じくJ.L.ベントリーの「プログラマのうちあけ話」に出ている(p.178)。 疑似コードで書かれたサンプルの一部である。
列 S を空に初期設定する
for J := N - M + 1 to N do
T := RandInt(1, J)
if T が S の要素でない then
S の先頭に T を追加する
else
S の中で T の直後に J を追加する。
ここで RandInt(L, U) は、L..U の範囲の一様な乱数（整数値）を 返す関数である。
これを Javascript 用に書き直した。 n > m > 0 で、n, m はどちらも整数である。
こちらの配列sは、連想配列ではなく、 順序のある通常の配列として扱っている。 JavaScript の Array 型の変数が利用できるメソッドのうち、 unshift と spliceを用いているのがミソだ。 S の先頭に T を追加するのが unshift メソッド、 S の中で T の直後に J を追加するのが splice メソッドである。
この説明をした当時、1999 年では、 「T が S の要素かどうかを判断するメソッドはありません。 別に定義する必要があります。」と書いた。そして、 高林哲さんの bk ブログにある、 配列操作の比較表を参考にするといいだろう。 と付け加えた。
しかし、JavaScript 1.5 以上では、 Array クラスに indexOf メソッドが追加されたので、 これを使うことができる。 T が S の要素かどうかを判断するメソッドは、S.indexOf(T) である。 S.indexOf(T) は、SがTの要素であれば、 その配列で最初に出現する位置を返す。 SがTの要素でなければ -1 を返す。
更にもうひとつ、ランダムに選択する JavaScript のプログラムでは、 表示の順序は不定である。一見ランダムに見えるが、 一様なランダム性は保証されない。 ランダムな順列では、一様なランダム性が保証される。(2007-10-13)
以下、JavaScript のプログラムを掲げていたが、 ランダムな配列を生成するプログラムにバグがあった。 n = m のとき最後尾は常に1となってしまうバグである。 御指摘してくださった imo758 さんに感謝する。(2007-10-08)
バグの原因は、splice 関数の仕様を誤って認識していたためである。 具体的には、要素の挿入位置を誤っていたためだ。 s.splice(pos, length, element1, element2, ...) は、 配列のpos番めからlengthで指定した数を取り除き、 その位置にelement1, element2, ... を追加する。 ここで、length = 0 のとき、指定した pos がどこになるか、もっと考えるべきだった。 私は pos の直後と認識していたがこれが誤りで、 正しくは pos の直前である。
var ary = new Array(3, 1, 0) ary.splice(3, 0, 4) // ⇒ 3, 1, 0, 4
上のように、末尾に4を挿入するには、 spliceメソッドの第１引数に3を指定する必要がある。 数値3は配列の位置からはみだすので抵抗があったのが、 私の仕様認識の遠因だ。
以下はランダムに文字列を表示するプログラムである。ただし重複を許す。 文字列に使える文字は文字列種類の欄で指定できる。
この項： (2020-12-20)
まりんきょ学問所 ＞
JavaScript 手習い ＞
ランダム集合とランダム順列
