Методы генерации случайного сочетания

Материал из Викиконспекты
Перейти к: навигация, поиск

Постановка задачи

Необходимо сгенерировать случайное сочетание из [math] n [/math] чисел с равномерным распределением вероятности, если есть в наличии функция для генерации случайного числа в заданном интервале.

Решение за время O(n2)

Алгоритм генерации

Псевдокод

Доказательство корректности алгоритма

Решение за время O(n)

Алгоритм генерации

Псевдокод

Доказательство корректности алгоритма

См. также

Источники