順列のランダムサンプリング
#アルゴリズム
Algorithms for Generating Small Random Samples. Vincent A. Cicirello. Technical Report ALG-24-008, Cicirello.org, May 2024.
https://reports.cicirello.org/24/008/
Arxiv: https://arxiv.org/abs/2405.12371
n 個の要素から要素数 k の順列をランダムにサンプルする問題を考える。
k = 2 (pair) の場合、以下のアルゴリズムで 0 以上 n 未満の値からなる順列$ (i, j)を$ O(1)の計算量でサンプルできる。
code:RandomPair
i ← Rand(n)
j ← Rand(n - 1)
if j = i then j = n - 1
return (i, j)
ここで、$ \mathrm{Rand}(n) は 0 以上 n 未満の値をランダムにサンプルする処理。
また k = 3 (triple) の場合、以下のアルゴリズムによって$ O(1)の計算量で効率良くサンプルできる。
code:RandomTriple
i ← Rand(n)
j ← Rand(n - 1)
k ← Rand(n - 2)
if k = j then k ← n - 2
if j = i then j ← n - 1
if k = i then k ← n - 1
return (i, j, k)
一般の k については以下のアルゴリズム等が知られている。
reservoir sampling:$ O(n)の時間計算量でサンプルする。
insertion sampling:$ O(k^2)の時間計算量でサンプルする。