ランダム生成まとめ - かんプリンの学習記録

メモ用なので適当に書く．

1以上M以下の整数からなる長さNの数列
1. 重複あり
2. 重複なし
N個からM個選ぶ組み合わせ
1以上M以下の整数からなる長さNの単調増加数列
総和がMとなる非負整数からなる長さNの数列
括弧列
二分木
ラベル付き木
次数列を持つグラフ
個数上限付き01列
N頂点M辺の連結グラフ
重複上限Kの数列
ラベル無し根付き木
ラベル無し木
N以下の素数
全域木
ライブラリ

1以上M以下の整数からなる長さNの数列

長さ ${N}$ ， ${1\leq A_i\leq M}$ である数列 ${A}$ を一様ランダムに生成する．

重複あり

数列の要素に重複があってもよい場合を考える．
各要素の生成確率を ${\dfrac{1}{M}}$ としてもよい．

重複なし

数列の要素が互いに異なる場合を考える．
前から順にまだ使ってない数を等確率で使う．

N個からM個選ぶ組み合わせ

1以上M以下の整数からなる長さNの数列と同じように選ぶ，順番は無視．

1以上M以下の整数からなる長さNの単調増加数列

N個からM個選ぶ組み合わせと同じ．

総和がMとなる非負整数からなる長さNの数列

${M}$ 個の"〇"と ${N-1}$ 個の"|"を並べるやつ．
${N+M-1}$ 個の"〇"から"|"にする ${N-1}$ 個を選ぶと考えるとN個からM個選ぶ組み合わせと同じ．

括弧列

バランスのとれた括弧列の一様ランダムな生成．いわゆる構成比法で生成する．

括弧列は，以下の図の右下から左上への経路と対応するため経路をランダムに生成することを考える．

毎回，上か右を選択して移動するが，どのような確率で選択すればよいか．
それは，「上に行った場合の残りの経路数」と「右に行った場合の残りの経路数」の比率で遷移の確率が決まる．

これを用いて，上を選択する確率を求めると，

${\dfrac{(N-M)(N+1)}{(N-M+1)(N+M)}}$

となる．ただし， ${N}$ は現在地から右上の点までの上方向の遷移回数で， ${M}$ は現在地から右上の点までの右方向の遷移回数．

初期値は，長さ ${2n}$ の括弧列を生成するとして， ${N=n,M=n}$ であり，
上を選ぶと ${N\leftarrow N-1}$ ，右を選ぶと ${M\leftarrow M-1}$ となる．

二分木

括弧列を ${(X)Y}$ として再帰させれば1対1対応が取れる．

ラベル付き木

prufer列と対応が取れるので1以上M以下の整数からなる長さNの数列を使う．

次数列を持つグラフ

与えられた次数列を持つグラフを一様ランダムに生成する．
Fast uniform generation of random graphs with given degree sequences

個数上限付き01列

${0}$ の数が ${A}$ 個以下， ${1}$ の数が ${B}$ 個以下の長さ ${N}$ の01列をできるだけ一様なランダム生成する．また，以下の条件を満たす．

${N\leq A+B}$
${0\leq A,B\leq N}$

${0}$ の個数を ${x(N-B\leq x\leq A)}$ と決めるとN個からM個選ぶ組み合わせとして生成できる．

${0}$ の個数が ${x}$ となる確率は，

${\displaystyle\frac{\binom{N}{x}}{\sum_{i=N-B}^{A}\binom{N}{i}}}$
となる．

${N}$ が小さければそのまま， ${N}$ が大きければラプラスの定理を用いることで計算できる．
境界は ${50}$ とかでいいかも．

N頂点M辺の連結グラフ

すぐに思いつく方法として， ${N}$ 頂点の木をランダム生成した後，辺の数が ${M}$ になるまでランダムに辺を追加するというものがある．しかしこれだと，全域木の数に無視できないほどの差があるため一様ランダムな生成とは言えない．

${N}$ 頂点 ${M}$ 辺の連結グラフを生成する方法はいくつかある．

生成検査法

${\binom{n}{2}}$ の辺から ${M}$ 本選んでグラフを作る．作ったグラフが連結なら終了．そうでなければまた生成を行う．

この方法は一様ランダムに生成できるが， ${N}$ と ${M}$ が近い場合，連結となる確率が低いため生成回数が増大する恐れがある．

全域木法

${N}$ 頂点の木を生成する[ラベル付き木の生成]．この木に ${M-N+1}$ 本の辺を追加する．

この方法は高速に生成できるが，一様ランダムにはならない．

構成比法

特定の性質を持つグラフの数に応じた確率を用いることで，比較的速く(それでもまだ遅い)，一様ランダムに生成できる．

構成比近似法

構成比法では構成比の計算に時間がかかっていた．構成比近似法では構成比の近似値を用いることで高速な生成が可能になる．ほぼ一様ランダムになる．
構成比近似法

重複上限Kの数列

${1}$ 以上 ${M}$ 以下の整数からなる長さ ${N}$ の数列であって，同じ数が出現する回数が ${K}$ 回以下であるものをランダム生成したい．

${N,M,K}$ が小さかったり， ${N << MK}$ かつ ${K}$ がある程度大きかったりすると生成検査法で高速に一様ランダムに生成できる．

${N=MK}$ のときは ${1}$ から ${M}$ まで順に，空いているところから ${K}$ 箇所選んで決めていく方法で一様ランダム生成できる．

${K=1}$ は使ってない整数から一つ選んで前から埋めていけばよい．

生成検査法で ${1}$ 回で条件を満たす確率は， ${1}$ 年が ${M}$ 日であり， ${N}$ 人のうち同じ誕生日の ${K+1}$ 人組が存在しない確率と同じ．(誕生日のパラドックス)

ラベル無し根付き木

https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=b169f11a617bab9395da9f880ce677ca520b2348
https://www2.math.upenn.edu/~wilf/website/CombinatorialAlgorithms.pdf

ラベル無し木

https://www2.math.upenn.edu/~wilf/website/Free%20trees.pdf
木の総数の近似

N以下の素数

${N}$ 以下の素数を一様ランダムに生成する
ミラーラビンを使った生成検査法
素数定理から比較的早く生成できることがわかる

全域木

与えられたグラフの全域木を一様ランダムに生成する．
http://jakub.tarnawski.org/slides_soda_2015.pdf ${O(M^{4/3})}$

ライブラリ

github.com

rand_lab_free_trees()	ラベル付き木の一様ランダム生成
rand_lab_rooted_trees()	ラベル付け根付き木の一様ランダム生成
rand_ulab_free_trees()	ラベル無し木の一様ランダム生成
rand_ulab_rooted_trees()	ラベル無し根付き木の一様ランダム生成