请教一下各类大佬, 这个概率题我错在哪里?

"""
从目标集合 S 中有放回地抽取 n 次, 计算子集 s 中的每个元素至少抽中 1 次的概率.
目标集合 S 为 [A, A, B, C...] 这种有重复的集合.
集合 s 为 S 的子集, 且 s 中不包含重复元素.
"""

import time
from typing import List
from random import Random
from functools import reduce


def frac(n):
    """
    n!
    """
    if n <= 1:
        return 1

    r = 1
    while n > 1:
        r *= n
        n -= 1
    return r


def calculate_probability(choices: List[str], targets: List[str], num_draw: int) -> float:
    """
    计算此概率:从目标集合 choices 中有放回地抽取 num_draw 次, targets 集合中每个元素至少抽中一个.
    targets 必须是 choices 的子集
    """
    num_choice = len(choices)
    num_target = len(targets)
    left_draw = num_draw - num_target
    targets = {t: choices.count(t) for t in targets}

    if left_draw < 0:
        print(f"0.0%")
        return 0.0

    # 目标集合每个选项出现的次数相乘, 为目标集合的可能数
    count = reduce(lambda x, y: x * y, targets.values())
    # 如果抽取次数大于目标集合个数, 则还可以再抽取若干次任意元素
    count *= (num_choice ** left_draw)
    # 以上获得的可能数是固定顺序下的, 所以总的可能数需要再乘以 num_draw 的阶乘
    count *= frac(num_draw)

    # 每次抽取有 num_choice 次可能, 总共抽取 num_draw 次
    total = num_choice ** num_draw
    p = round(count / total * 100, 2)

    print(f"{p}%")
    return p


def observe_probability(choices, targets, num_draw) -> float:
    """
    观察此概率:从目标集合 choices 中有放回地抽取 num_draw 次, targets 集合中每个元素至少抽中一个.
    targets 必须是 choice 的子集.
    """

    rand = Random()
    rand.seed(time.time() * 1000)
    count = 0
    total = 1000000

    # 模拟 total 次
    for num_test in range(total):
        targets = {t: 0 for t in targets}

        # 每次模拟抽取 num_draw 次
        for draw in range(num_draw):
            choice = rand.choice(choices)
            if choice in targets:
                targets[choice] += 1

        values = list(targets.values())
        match = all(map(lambda x: x >= 1, values))
        if match:  # 所有目标都抽到, 计数加 1
            count += 1

    p = round(count / total * 100, 2)
    print(f"{p}%")

    return p


def test():
    choices = [
        "A", "A", "A", "A",
        "B", "B", "B", "B",
        "C", "C", "C", "C",
        "D",
        "E",
    ]
    targets = ["A", "B", "C", "D"]
    num_draw = 5

    observe_probability(choices, targets, num_draw)
    calculate_probability(choices, targets, num_draw)


if __name__ == "__main__":
    test()

gulu

2021-01-29 10:05:34 +08:00

@necomancer
老哥，我初步看了一下“集券”问题，感觉和我这个问题有点不一样。

集券问题：
Given n coupons, how many coupons do you expect you need to draw with replacement before having drawn each coupon at least once?
有 n 张优惠券，有放回地抽取多少次，才能保证每张券抽取到至少一次？

我的问题：
有 N 张优惠券，不平均地分类为 n 种。有放回地抽取多少次，才能保证 m 种优惠券至少抽取到一次？