211小R的并集大小期望计算

题解

小 R 有n个集合，每个集合中的元素都是唯一的且互不相同。她希望通过随机选择两个集合，并计算它们的并集大小，来求出并集大小的期望值。结果需要保留两位小数。题目保证输入至少有两个集合。

问题分析

要计算随机选择两个集合的并集大小的期望值，关键在于确定每个元素在这两个集合的并集中出现的概率。具体步骤如下：

1. 元素出现次数统计：

   • 首先统计每个元素在所有集合中出现的次数。即，元素x出现于v个不同的集合中。

2. 计算每个元素在并集中出现的概率：

   • 对于一个元素x，它至少出现在所选的两个集合中的一个的概率，可以通过以下公式计算：
     $$
     P(x \text{ 出现在并集中}) = 1 - P(x \text{ 不出现在两个集合中})
     $$

   • x不出现在两个集合中的概率为：

     $$
     P(x \text{ 不出现在两个集合中}) = \frac{\binom{n - v}{2}}{\binom{n}{2}}
     $$

     其中，(\binom{n}{2}) 表示从n个集合中选取两个集合的组合数。

   • 因此，x出现在并集中的概率为：
     $$
     P(x \text{ 出现在并集中}) = 1 - \frac{(n - v) \times (n - v - 1)}{n \times (n - 1)}
     $$

3. 计算期望值：

   • 期望值为所有元素在并集中出现概率的总和，即：
     $$
     \text{期望值} = \sum_{x} P(x \text{ 出现在并集中})
     $$

4. 结果格式化：

   • 最终的期望值需要保留两位小数。

代码解析

from collections import Counter

def solution(n: int, st: list) -> str:
    # 统计所有元素在所有集合中出现的次数
    cnt = Counter([i for s in st for i in s])
    res = 0
    for k, v in cnt.items():
        # 对于每个元素，计算其出现在并集中的概率，并累加到结果中
        res += n * (n - 1) - (n - v) * (n - v - 1)
    # 计算期望值并格式化为两位小数
    return "{:.2f}".format(res / (n * (n - 1)))

if __name__ == '__main__':
    print(solution(2, [[1, 2], [1, 3, 5]]) == '4.00')      # 输出: True
    print(solution(3, [[1, 4], [2, 5], [3, 6, 7]]) == '4.67')  # 输出: True
    print(solution(2, [[10, 20, 30], [10, 30, 50, 70]]) == '5.00')  # 输出: True