1からnまでの乱数をm個重複せずランダムに選ぶ

keyword:

カートに追加

overview

1からnまでの乱数をm個重複せずランダムに選ぶ. このアルゴリズムは空間計算量O(m),時間計算量O(m)で済む(ハッシュ操作をO(1)とする). 簡単な実装方法として - 重複しないm個を取り出すまで乱数を引く (n>>m なら衝突しにくいので高速) - iotaしてshuffleしてeraseする(空間O(n),時間O(n)) があるが,計算量的には両者のどちらよりも優れていることが分かる. m/nの比でアルゴリズムを選択するハイブリッド実装でも良さそうである. [TODO] rand_int の除去

usage

void pick_multirand(int n, int m, vector& out)
; 1からnまでの乱数をm個重複せずランダムに選びoutにpush_backする
inline int RandChooser::operator()(RANDOM &rd)
rd : 乱数生成器.
; 乱数生成する.
inline int RandChooser::disable(int idx)
; 整数idxを次回以降の乱数生成で選ばれないように設定する.
; 既にdisableした値をもう一度disableする操作はinvalid.

code