生成した複数件のランダムな文字列において重複が発生しない確率は□％

はじめに

2019新卒 エンジニア Advent Calendar 2019 19 日目の記事です。

ソフトウエア開発において、ランダムな文字列を生成することがあります。例えば、アカウントの識別子（ID）という役割で利用されます。具体例としてTwitterでは、ユーザがアカウントを作成すると、長さ15のランダムな文字列をIDとして付与します。しかし、このような役割があるがゆえに、ランダムな文字列は重複してはいけません。それゆえ、万が一重複が発生したときに実行する相応の処理などもあるかと思います。

新卒として入社して以降、このような重複のないランダムな文字列を必要とするテストデータを作成する機会がありました。その時の興味として抱いていた、そもそもどれだけの確率で重複が発生するのか（上記、それ相応の処理が実行されることはあるのか）を明らかにしたいと思います。

※タイトルはトリビアの種のオマージュです。懐かしい番組ですね。🧠

実験

計算式

結果は以下の計算式で算出できます。

P = \prod_{k = 0}^{n} \frac{(c^l)-k}{c^l}

上記に示した計算式の各変数は以下の通りです。

• c ・・・ランダムな文字列を構成する文字の種類
• n ・・・ランダムな文字列の件数
• l ・・・ランダムな文字列の長さ
• P ・・・重複が発生しない確率

実数による確率の算出

今回の実験におけるランダムな文字列は、数字と英字（小文字）の合計36種の文字から構成されるものと定義します。（例：長さ10の場合、yttrj4ca8n）この場合、以下の計算式によって重複が発生しない確率が算出できます。

P = \prod_{k = 0}^{n} \frac{(36^l)-k}{36^l}

また今回の実験における他変数の値は以下とします。

• n ・・・100，10000，1000000
• l ・・・5，10，15

はじめに、以下の実数を当てはめます。Pythonのプログラムで計算します。

n = 100, 
l = 5

c = 36
n = 100
l = 5
P = 1

for k in range( n ):
    P = P * ((c ** l) - k) / (c ** l)

print(P)

0.999918139356006

重複が発生しない確率は99%以上ですね。

まとめて算出し、比較してみます。

• 行：文字数
• 列：件数

	5	10	15
100	0.999918139356006	0.9999999999986461	1.0
10000	0.4374156133080636	0.9999999863258114	1.0
1000000	1.5e-322	0.9998632539253056	1.0

文字数10や15の場合ほとんど重複は発生しないようです。特に15は自分の環境におけるpythonによる計算ではわからない確率なんですね。

おわりに

ソフトウエア開発において、生成することもあろうランダムな文字列の生成について、重複が発生しない確率を算出しました。文字数が5だと少々怪しいですが、10や15の場合、100万件のランダムな文字列を精製したとしても、重複はほとんど発生しないことがわかりました。しかし、念には念をということで対応する処理の準備は必要ですね。

しかし、ここで強運を使ってしまうことだけは避けたいな…

（2019年12月20日追記）
以下の記事に掲載していただきました！ありがとうございます！

• 【Python】Qiita 週間ストック数ランキング【自動更新】（2019年12月19日 13時00分更新 ）