Изменения

==Постановка задачи={{Задача|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> раз.

===Псевдокод=== randomCombination(arrayOfElements, n, k) for i = 1 to k r = rand(1..Решение за время <tex>O(n - i + 1)nk); cur = 0; for j = 1 to n if exist[j] cur++; if cur == r res[i] </tex>= arrayOfElements[j]; exist[j] = false; sort(res); return res;

Здесь Пусть <tex>exist[]S</tex> — такой массив, что если множество из <tex>exist[i] == 1n</tex>элементов, то <tex>i</tex> тогда для генерации случайного сочетания сделаем следующее:* '''Шаг 1.''' Выберем в множестве случайный элемент присутствует ,* '''Шаг 2.''' Добавим его в множестве Sсочетание,* '''Шаг 3.''' Удалим элемент из множества.

Сложность алгоритма Эту процедуру необходимо повторить <tex>k</tex> раз.===Псевдокод===*<tex>\mathtt{arrayOfElements}</tex> — массив, в котором находятся все элементы множества <tex>\mathtt{S}</tex>,*<tex>\mathtt{exist}</tex> — такой массив, что если <tex>\mathtt{exist[i] == 1}</tex>, то <tex>O\mathtt{i}</tex> элемент присутствует в множестве <tex>\mathtt{S}</tex>,<code> '''int[]''' randomCombination('''int[]''' arrayOfElements, '''int''' n, '''int''' k): '''for''' i = 1 '''to''' k r = random(1, (n^2- i + 1)) cur = 0 '''for''' j = 1 '''to''' n '''if''' exist[j] cur = cur + 1 '''if''' cur == r res[i] = arrayOfElements[j] exist[j] = false sort(res) '''return''' res</texcode>

На первом шаге мы выбираем один элемент из <tex>n</tex>, на втором из <tex>n - 1</tex>, ..., <tex>\dots</tex> на <tex>k</tex>-ом из <tex>n - k + 1</tex>. Тогда общее число исходов получится <tex>n \times (n - 1) \times ... \dots \times (n - k + 1)</tex>. Это эквивалентно <tex dpi="180">{n! \over (n - k)!}</tex>. Однако заметим, что на этом шаге у нас получаются лишь размещения из <tex>n</tex> по <tex>k</tex>. Но все эти размещения можно сопоставить одному сочетанию, отсортировав их. И так как размещения равновероятны, и каждому сочетанию сопоставлено ровно <tex>k!</tex> размещений, то сочетания тоже генерируются равновероятно.

==Решение за время <tex>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_shufflerandomShuffle(a); <font color=darkgreen> //randomShuffle() — функция генерации случайной перестановки</font color=darkgreen> '''for ''' i = 1 '''to ''' n '''if ''' a[i] == 1 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а]]. Следовательно, сложность и всего алгоритма <tex>O(n)</tex>

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

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

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