Методы генерации случайного сочетания — различия между версиями
Loboda (обсуждение | вклад) м |
Loboda (обсуждение | вклад) м |
||
| Строка 3: | Строка 3: | ||
==Решение за время O(n<sup>2</sup>)== | ==Решение за время O(n<sup>2</sup>)== | ||
| + | |||
| + | Комментарий | ||
| + | |||
===Алгоритм генерации=== | ===Алгоритм генерации=== | ||
| Строка 16: | Строка 19: | ||
==Решение за время O(n)== | ==Решение за время O(n)== | ||
| + | |||
| + | Комментарий | ||
| + | |||
===Алгоритм генерации=== | ===Алгоритм генерации=== | ||
| Строка 25: | Строка 31: | ||
===Доказательство корректности алгоритма=== | ===Доказательство корректности алгоритма=== | ||
| + | |||
| + | |||
| + | |||
| + | ===Оценка временной сложности=== | ||
| Строка 30: | Строка 40: | ||
== См. также == | == См. также == | ||
| − | + | *[[Метод генерации случайной перестановки, алгоритм Фишера-Йетса]] | |
== Источники == | == Источники == | ||
| − | + | *[http://www.rsdn.ru/article/alg/Combine.xml#ECPAC RSDN - Генерация случайных сочетаний. Генерация сочетания по его порядковому номеру] | |
[[Категория: Дискретная математика и алгоритмы]] | [[Категория: Дискретная математика и алгоритмы]] | ||
[[Категория: Комбинаторика]] | [[Категория: Комбинаторика]] | ||
Версия 20:17, 26 декабря 2012
Содержание
Постановка задачи
Необходимо сгенерировать случайное сочетание из чисел с равномерным распределением вероятности, если есть в наличии функция для генерации случайного числа в заданном интервале.
Решение за время O(n2)
Комментарий
Алгоритм генерации
Псевдокод
Доказательство корректности алгоритма
Решение за время O(n)
Комментарий
