生日问题的算法

这个例子演示了一个算法的实现和应用，该算法解决了广义生日问题-确定一个组中的最小数量，在该组中匹配一定数量的人的生日的概率超过给定的

导言

什么是"生日挑战"？

"生日问题"是概率论中的一个经典问题，其表述如下：一个群体中至少有两个人拥有相同生日的概率是多少？

通常，该任务是针对对此概率超过50％的最小数量感兴趣的人群进行研究的。然而，它可以扩展：您可以搜索，例如，最小数量的人匹配的生日三，四等。

原始问题在密码学和随机性测试中有重要的应用，在那里它被用来评估碰撞的可能性。

主要部分

用于计算一组的概率的函数 groupsize 一个人至少 sharers 一个人有相同的生日。使用重复次数的蒙特卡洛方法。 nrep.

function equalbirthdays(sharers::Int, groupsize::Int; nrep::Int = 10000)
    eq = 0 # Счётчик случаев, когда найдено нужное совпадение
    for _ in 1:nrep
        # Генерируем случайные дни рождения для всех людей в группе
        group = rand(1:365, groupsize)
        # Преобразуем массив в множество - чтобы убрать повторы
        grset = Set(group)
        # Условие: дубликатов должно быть достаточно, чтобы
        # хотя бы `sharers` человек имели одинаковый день рождения
        if groupsize - length(grset) ≥ sharers - 1 &&
            any(count(x -> x == d, group) ≥ sharers for d in grset)
            eq += 1
        end
    end
    return eq / nrep # Возвращаем частоту успеха
end

equalbirthdays

我们从一组2人开始，假设最小尺寸。

gsizes = [2]

# Для каждого числа людей, у которых должен совпадать день рождения
for sh in (2, 3, 4, 5)
    local gsize = gsizes[end] # Начальное приближение
    local freq # Переменная для хранения частоты события

    # Первый этап: грубый поиск (меньше итераций для быстрой оценки)
    while equalbirthdays(sh, gsize; nrep = 100) < 0.5
        gsize += 1
    end

    # Второй этап: более точный поиск в небольшом диапазоне
    for gsize in trunc(Int, gsize - (gsize - gsizes[end]) / 4):(gsize + 999)
        if equalbirthdays(sh, gsize; nrep = 250) > 0.5
            break
        end
    end

    # Третий этап: точный подсчёт с высокой точностью
    for gsize in (gsize - 1):(gsize + 999)
        freq = equalbirthdays(sh, gsize; nrep = 50000)
        if freq > 0.5
            break
        end
    end

    # Сохраняем найденное число людей
    push!(gsizes, gsize)

    # Вывод результата
    @printf("%i людей в группе из %s имеют общий день рождения с вероятностью %5.3f\n", sh, gsize, freq)
end

2 людей в группе из 22 имеют общий день рождения с вероятностью 0.511
3 людей в группе из 86 имеют общий день рождения с вероятностью 0.501
4 людей в группе из 181 имеют общий день рождения с вероятностью 0.504
5 людей в группе из 305 имеют общий день рождения с вероятностью 0.502

结论

我们已经考虑了解决广义生日问题的算法的实现：计算具有给定概率（在这种情况下，超过50％）匹配生日所需的最小数量。 k 人类。

该算法使用蒙特卡洛方法进行统计概率估计，这使得它适用于复杂或分析上难以计算公式的情况。

这种方法不仅在概率论中有用，而且在评估巧合或碰撞可能性很重要的其他领域也有用（例如，在散列中）。

该示例是使用[Rosetta代码]的材料开发的（https://rosettacode.org/wiki/Birthday_problem ）