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

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

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

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

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

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

Псевдокод

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

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

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

Псевдокод

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

См. также

Источники

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Методы_генерации_случайного_сочетания&oldid=28454»