はじめに
この記事は、LIGHTzアドベントカレンダー2022の23日目の記事です。
クリスマスまであと2日でございます．
@KTasknこと、たすく、です。16日目の解答になります．出題と解答で２日稼ぎます．今日も結局日付変わる前の投稿です．間に合うのかクリスマスイブになってしまうぞ，
改題前
そもそも，このネタはアルゴリズムの講義ででた問題の改題なので，その改題前がどのようになっていたかを話すと，
問題（改題前）
改行を含むテキストファイルが存在する．このファイルの行数$N$は未知である．
このファイルから等しくランダムに１行を抜き出し，出力するプログラムを示せ．
ただし，ファイルは先頭から１行ずつしか読み込めず，また記憶域（メモリ）は１行までしか読み込めない．
はい．出題時とは異なりすごくアルゴリズムぽい問題ですね．これなら見聞きしたことある方もいるのではないでしょうか．
解答
それまでに選んでいた行を$l_{\text{save}}$、ステップ$k$に読み込まれた行を$l_k$とする。
ステップ$k$で$l_k$を$\frac{1}{k}$、$l_{\text{save}}$を$\frac{k-1}{k}$の確率で選択するとき、ステップ$k-1$において、すべての行が等しく$\frac{1}{k-1}$の確率で$l_{\text{save}}$として選択されたことを示せば、$\frac{1}{k-1} \frac{k-1}{k} = \frac{1}{k}$となり、ステップ$k$においてもすべての行が等しく$\frac{1}{k}$で選ばれることを示せる。
ステップ1において、$l_{1}$が1の確率で$l_{\text{save}}$に選択される。
ステップ2において、$l_{1}$と$l_2$は等しく$\frac{1}{2}$の確率で$l_{\text{save}}$に選択される。
よって、上記の条件を満たし、それぞれの行が$\frac{1}{k}$で選ばれることが示せた。
pythonでの実装を示す
from random import random
import collections
def randline(k):
# k行のテキストファイルの代わりにk個からなるlistを作成する
textfile = range(1, k+1)
for i in textfile:
if random() < 1 / i:
# 記憶域はselectingのみ
selecting = i
else:
pass
return selecting
if __name__ == "__main__":
# 試行回数
N = 100000
# 真の行数(実際は未知）
NUM_LINE = 50
print(
# N回試行し，均等に出力されるか確認する
sorted(collections.Counter([
randline(NUM_LINE)
for i in range(N)
]).items(), key=lambda key: key[0]
))
以上．解けたでしょうか？