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

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

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

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

Комментарий

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

Псевдокод

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

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

Комментарий

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

Псевдокод

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

Оценка временной сложности

См. также

• Метод генерации случайной перестановки, алгоритм Фишера-Йетса

Источники

• RSDN - Генерация случайных сочетаний. Генерация сочетания по его порядковому номеру