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

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

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

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

Псевдокод

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

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

Для более быстрого решения данной задачи воспользуемся следующим алгоритмом: пусть задан для определенности массив [math]a[][/math] размера [math]n[/math], состоящий из [math]k[/math] единиц и [math]n - k[/math] нулей. Применим к нему алгоритм генерации случайной перестановки. Тогда все элементы [math]i[/math], для которых [math]a[i] = 1[/math], включим в сочетание.

Псевдокод

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

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

См. также

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

Источники

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