Изменения
Нет описания правки
Необходимо сгенерировать случайное сочетание из <tex> n </tex> элементов по <tex> k </tex> с равномерным распределением вероятности, если есть в наличии функция для генерации случайного числа в заданном интервале.
}}
==Решение за время <tex>O(n ^ 2)</tex>==
Пусть <tex>S</tex> — массив из <tex>n</tex> элементов, тогда для генерации случайного сочетания сделаем следующее:
* отсортируем <tex>S</tex>,
* запишем в массив <tex>C</tex> первые <tex>k</tex> элементов(это первое сочетание),
* выберем случайные номер сочетания <tex>r</tex>,
* применим алгоритм генерации следующего сочетания <tex>r - 1</tex> раз к массиву <tex>C</tex>.
===Псевдокод===
<code>
randomCombination(S, n, k)
sort(S);
'''for''' i = 1 '''to''' k
C.push_back(S[i])
r = rand(1, n! / (k!(n - k)!))
'''for''' i = 1 '''to''' r - 1
next_Combination(C, n, k)
'''return''' res
</code>
==Решение за время <tex>O(n ^ 2)</tex>==
