Изменения

==Постановка задачи={{Задача|definition =Необходимо сгенерировать случайное сочетание из <tex> n </tex> элементов по <tex>k</tex> с равномерным распределением вероятности, если есть в наличии функция для генерации случайного числа в заданном интервале. }}

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

Пусть <tex>S - </tex> — множество из <tex>n </tex> элементов, тогда для генерации случайного сочетания сделаем следующее:* '''Шаг 1.''' Запишем в массив <tex>C</tex> числа от <tex>1</tex> до <tex>k</tex>,* '''Шаг 2.''' Выберем в множестве случайный элементномер сочетания <tex>r</tex>,* '''Шаг 3.''' Применим алгоритм [[Получение следующего объекта|получение следующего сочетания]] <tex>r - 1</tex> раз к массиву <tex>C</tex>,* Добавим его '''Шаг 4.''' В <tex>C</tex> хранятся номера позиции из <tex>S</tex> входящих в случайное сочетание, запишем в <tex>C</tex> эти элементы.===Псевдокод===* Удалим элемент из <tex>\mathtt{arrayOfElements}</tex> — массив, в котором находятся все элементы множества<tex>\mathtt{S}</tex>.<code> '''int[]''' randomCombination('''int[]''' arrayOfElements, '''int''' n, '''int''' k): '''for''' i = 1 '''to''' k C[i] = i r = random(1, n! / (k!(n - k)!)) <font color=darkgreen> //random(1, i) генерирует случайное целое число в интервале [1..i]</font color=darkgreen> '''for''' i = 1 '''to''' r - 1 nextCombination(C, n, k) <font color=darkgreen> //nextCombination(C, n, k) генерирует следующие сочетание</font color=darkgreen> '''for''' i = 1 '''to''' k C[i] = arrayOfElements[C[i]] '''return''' C</code>

Эту процедуру необъодимо повторить Сложность алгоритма — <texdpi="150">O({n! \over k!(n - k)!} \cdot n)</tex> раз.

*<tex>\mathtt{arrayOfElements}</tex> — массив, в котором находятся все элементы множества <tex>\mathtt{S}</tex>,*<tex>\mathtt{exist}</tex> — такой массив, что если <tex>\mathtt{exist[i] == 1}</tex>, то <tex>\mathtt{i}</tex> элемент присутствует в множестве <tex>\mathtt{S}</tex>,<code> '''int[]''' randomCombination('''int[]''' arrayOfElements, '''int''' n, '''int''' k): '''for''' i = 1 '''to''' k r = randrandom(1.., (n- i + 1);) cur = 0; '''for''' j = 1 '''to''' n '''if''' exist[j] cur = cur++;1 '''if''' cur == r insertInAns(a res[i] = arrayOfElements[j]); exist[j] = false; sort(res) '''return''' res</code>

 ==Решение за время O(n)== Для более быстрого решения данной задачи воспользуемся следующим алгоритмом: пусть задан для определенности массив <tex>a[]</tex> размера <tex>n</tex>, состоящий из <tex>k</tex> единиц и <tex>n - k</tex> нулей. Применим к нему [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса|алгоритм генерации случайной перестановки]]. Тогда все элементы <tex>i</tex>, для которых <tex>a[i] = 1</tex>, включим в сочетание. 

'''int[]''' randomCombination('''int[]''' arrayOfElements, '''int''' n, '''int''' k): '''for''' i = 1 '''to''' n '''if''' i <= k a[i] = 1; '''else''' a[i] = 0; random_shuffle randomShuffle(a); <font color=darkgreen> //randomShuffle() — функция генерации случайной перестановки</font color=darkgreen> '''for''' i = 1 '''to''' n '''if''' a[i] == 1 insertInAnswer ans.push(arrayOfElement[i]); '''return''' ans

 Заметим, что всего перестановок <tex>n!</tex>, но так как наш массив состоит только из <tex>0</tex> и <tex>1</tex>, то перестановка только <tex>0</tex> или только <tex>1</tex> ничего в нем не меняет. Заметим, что число перестановок нулей равно <tex>(n - k)!</tex>, единиц — <tex>k!</tex>. Следовательно, всего уникальных перестановок — <tex dpi = "180">{n! \over k!(n - k)!}</tex>. Все они равновероятны, так как была сгенерирована случайная перестановка, а каждой уникальной перестановке сопоставлено ровно <tex>k!(n - k)!</tex> перестановок. Но <tex dpi="180">{n! \over k!(n - k)!}</tex> — число сочетаний из <tex>n</tex> по <tex>k</tex>. То есть каждому сочетанию сопоставляется одна уникальная перестановка. Следовательно, генерация сочетания происходит также равновероятно.

Заметим, что алгоритм Алгоритм состоит из 2 двух невложенных циклов по <tex>n</tex> итераций каждый и функции генерации случайной перестановки <tex>random\_shufflemathrm{randomShuffle()}</tex>, работающей за <tex>O(n)</tex> по алгоритму [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса|Фишера ЙетcаФишера—Йетcа]]. Следовательно, временная сложность и всего алгоритма <tex>O(n)</tex>

*[[Метод генерации случайной перестановки, алгоритм Фишера-ЙетсаПолучение номера по объекту|Получение номера по объекту]]*[[Генерация комбинаторных объектов в лексикографическом порядке]]

== Источники информации ==

*[http://www.rsdn.ru/article/alg/Combine.xml#ECPAC RSDN - Герасимов В. А. — Генерация случайных сочетаний. Генерация сочетания по его порядковому номеру]