わさっきhb

大学（教育研究）とか ，親馬鹿とか，和歌山とか，とか，とか．

1〜NからM個をランダムに選ぶ

Ruby

イロモネアの一般人審査員*1の番号の決め方は，

  • 1〜20から1人
  • 21〜40から1人
  • 41〜60から1人
  • 61〜80から1人
  • 81〜100から1人

っぽい．一度，そうでないのも見かけたような気がするのですが．
そういえば，ビンゴカードの番号は，左の列から順に

  • 1〜15から5個
  • 16〜30から5個
  • 31〜45から4個*2
  • 46〜60から5個
  • 61〜75から5個

ですね．共通化するプログラムが作れそうです．
そのプログラムは日を改めるとして，まずはビンゴゲームのための乱数生成から．仕様は次のとおり．

1〜Nから異なるM個の数をランダムに取り出し，小さいものから順に出力しなさい．ただし，N≧Mとします．また，ソートの使用を禁じます．

仕様の最後は，「O(N)で処理する」のほうが分かりやすいかもしれません．ただ，後述のプログラムでは，Array#<< (配列へpush)を使っていて，これの手間がO(1)かどうかはわかっていませんので，O(N)は目指さないものとします．
このアルゴリズムは，『珠玉のプログラミング―本質を見抜いたアルゴリズムとデータ構造』に書いてあったのを覚えています．思い出しながら書いてみると，

  • 初期値はn=N, m=Mとします．
  • 1から順に，m/nの確率で(乱数と比較して)選びます．
  • 一つ選んだら，mの値を1減らします．
  • 選ぶ選ばないにかかわらず，nの値を1減らします．
  • mが0になったら，M個を選んだということで，処理を終えます．

プログラムを示します．chooseの引数は，コメントにあるとおりです．ビンゴカードへの応用を念頭に置いています．

#!/usr/bin/env ruby

# choose1.rb

def choose(max, pcs, ofst = 1)
  # ofst〜(ofst + max - 1)からpcs個をランダムに取り出し配列にして返す
  # ソートは使用しない
  array = []

  while pcs > 0
    r = rand
    print "%2d: %6.3f * %2d = %6.3f <=> %d" % [ofst, r, max, r * max, pcs] if $DEBUG
    if r * max < pcs
      array << ofst
      pcs -= 1
      print " (chosen)" if $DEBUG
    end
    puts if $DEBUG

    max -= 1
    ofst += 1
  end

  array
end

if __FILE__ == $0
  max = (ARGV.shift || 15).to_i
  pcs = (ARGV.shift || 5).to_i
  ofst = (ARGV.shift || 1).to_i
  p choose(max, pcs, ofst)
end

そして何度か実行．

$ ruby choose1.rb
[4, 5, 6, 9, 15]
$ ruby choose1.rb
[1, 2, 7, 9, 10]
$ ruby choose1.rb
[3, 4, 6, 7, 8]
$ ruby -d choose1.rb 
 1:  0.474 * 15 =  7.103 <=> 5
 2:  0.691 * 14 =  9.678 <=> 5
 3:  0.062 * 13 =  0.807 <=> 5 (chosen)
 4:  0.118 * 12 =  1.411 <=> 4 (chosen)
 5:  0.974 * 11 = 10.714 <=> 3
 6:  0.291 * 10 =  2.914 <=> 3 (chosen)
 7:  0.808 *  9 =  7.271 <=> 2
 8:  0.214 *  8 =  1.714 <=> 2 (chosen)
 9:  0.713 *  7 =  4.989 <=> 1
10:  0.076 *  6 =  0.453 <=> 1 (chosen)
[3, 4, 6, 8, 10]

ランダムっぽいです．回数を指定して生成させ，各値の出現回数を比較してみましょう．無作為性の検証には程遠いですが，まあ手軽なチェックということで．

#!/usr/bin/env ruby

# choose2.rb

def choose(max, pcs, ofst = 1)
  # ofst〜(ofst + max - 1)からpcs個をランダムに取り出し配列にして返す
  # ソートは使用しない
  array = []

  while pcs > 0
    r = rand
    print "%2d: %6.3f * %2d = %6.3f <=> %d" % [ofst, r, max, r * max, pcs] if $DEBUG
    if r * max < pcs
      array << ofst
      pcs -= 1
      print " (chosen)" if $DEBUG
    end
    puts if $DEBUG

    max -= 1
    ofst += 1
  end

  array
end

if __FILE__ == $0
  max = (ARGV.shift || 15).to_i
  pcs = (ARGV.shift || 5).to_i
  ofst = (ARGV.shift || 1).to_i

  if ARGV.empty?
    p choose(max, pcs, ofst)
  else
    t = (ARGV.shift || 100).to_i
    h = Hash.new(0)
    t.times do |t|
      choose(max, pcs, ofst).each do |j|
        h[j] += 1
      end
    end
    p h
  end
end

動作確認．

$ ruby choose2.rb 15 5 1 300
{5=>101, 11=>95, 6=>89, 1=>102, 12=>102, 7=>95, 2=>105, 13=>110, 8=>106, 3=>93, 14=>105, 9=>119, 15=>82, 4=>95, 10=>101}
$ ruby choose2.rb 15 5 1 3000
{5=>966, 11=>1035, 6=>985, 1=>992, 12=>1044, 7=>942, 13=>1036, 2=>1077, 8=>1007, 14=>993, 3=>1028, 9=>991, 4=>958, 15=>994, 10=>952}
$ ruby choose2.rb 15 5 1 30000
{5=>9997, 11=>9965, 6=>10029, 1=>10018, 12=>10025, 7=>10024, 2=>9862, 13=>9943, 8=>10032, 14=>10056, 3=>10064, 9=>10028, 4=>10026, 15=>10024, 10=>9907}
$ ruby choose2.rb 15 5 1 300000
{5=>100487, 11=>100210, 6=>99494, 1=>99906, 12=>99899, 7=>99527, 2=>100126, 13=>100003, 8=>99821, 3=>100200, 14=>100241, 9=>100112, 4=>99786, 15=>100025, 10=>100163}

まあまあええんやないでしょうか．
ところで，選択のための乱数生成は「r = rand」として，0以上1未満の実数値を求めていますが，Rubyのrandは整数値を生成できますので，「r = rand(max)」に置き換え，比較のところは「r * max < pcs」に替えて単に「r < pcs」にしても，同じように動作し，出現回数のチェックでも，偏りは見られませんでした．300000万回*3繰り返すと，処理時間は十数%減りました．ビンゴカードの乱数生成プログラムには，こちらを使うことにします．

*1:お笑い番組のイロモネアの審査員の一般人はエキストラですか？自分は昔エキ... - Yahoo!知恵袋にhttp://ameblo.jp/alf-131/entry-10102910710.html．へえ．

*2:真ん中が"FREE"になるため．

*3:恥ずかしい誤記ですが，そのまま残します．もちろん正しくは「300000回」です．