Pythonでkサイズの組み合わせから文字「a」を取得する確率を求めるプログラム

本記事では、n個の英字を含む配列と整数kが与えられたとき、k個の異なるインデックス（1始まり）を一様な確率で選択した場合に、選ばれたインデックスの中に少なくとも1つ文字「a」が含まれる確率を求めるPythonプログラムを紹介します。

問題の概要

例えば、letters = ['a', 'c', 'a', 'b', 'l', 'a', 'b', 'z']、k = 2 の入力が与えられた場合を考えてみましょう。8つの要素から2つを選ぶ組み合わせは全部で28通り存在します。このうち、(1,2)、(1,3)、(6,7) のように少なくとも1つに「a」が含まれる組み合わせは18通りあります。したがって、求める確率は 18/28 = 0.6428、すなわち約64.28%となります。

解法のアプローチ

この問題は、以下の手順で解くことができます。

• カウンタ変数 contain（「a」を含む組み合わせ数）と total（全組み合わせ数）を0で初期化する
• itertools.combinations を使って、letters から k 個を選ぶすべての組み合わせ c を列挙する
• c に「a」が含まれていれば contain を1増やす
• 各組み合わせごとに total を1増やす
• 最後に contain / total を返す

実装例

以下が実際のPythonコードです。

from itertools import combinations

def solve(letters, k):
    contain = 0
    total = 0

    for c in combinations(letters, k):
        if "a" in c:
            contain += 1
        total += 1
    return contain / total

letters = ['a', 'c', 'a', 'b', 'l', 'a', 'b', 'z']
k = 2
print(solve(letters, k))

入力

['a', 'c', 'a', 'b', 'l', 'a', 'b', 'z'], 2

出力

0.6428571428571429

出力値 0.6428... を百分率に直すと約64.28%となり、期待どおりの結果が得られます。

補足：数学的な計算方法

組み合わせを全列挙する代わりに、余事象を使った数学的な計算も可能です。「a」が含まれない確率は、「a」以外の文字だけから k 個を選ぶ確率なので、次の式で表せます。

確率 = 1 - C(n - a_count, k) / C(n, k)

ここで n は配列の長さ、a_count は「a」の出現回数、C は二項係数（組み合わせの総数）です。Pythonでは math.comb 関数を使うことで簡潔に実装できます。配列が非常に大きい場合は、こちらの方法の方が効率的です。