1632
правки
Изменения
м
==Постановка задачи={{Задача|definition =Необходимо сгенерировать случайное сочетание из <tex> n </tex> элементов по <tex>k</tex> с равномерным распределением вероятности, если есть в наличии функция для генерации случайного числа в заданном интервале. }}
Эту процедуру необъодимо повторить Сложность алгоритма — <texdpi="150">O({n! \over k!(n - k)!} \cdot n)</tex> раз.
==Решение за время O(n)== Для более быстрого решения данной задачи воспользуемся следующим алгоритмом: пусть задан для определенности массив <tex>a[]</tex> размера <tex>n</tex>, состоящий из <tex>k</tex> единиц и <tex>n - k</tex> нулей. Применим к нему [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса|алгоритм генерации случайной перестановки]]. Тогда все элементы <tex>i</tex>, для которых <tex>a[i] = 1</tex>, включим в сочетание.
Заметим, что алгоритм Алгоритм состоит из 2 двух невложенных циклов по <tex>n</tex> итераций каждый и функции генерации случайной перестановки <tex>random\_shufflemathrm{randomShuffle()}</tex>, работающей за <tex>O(n)</tex> по алгоритму [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса|Фишера ЙетcаФишера—Йетcа]]. Следовательно, временная сложность и всего алгоритма <tex>O(n)</tex>
rollbackEdits.php mass rollback
==Решение за время O(n<sup>2</sup>)Наивное решение==
Пусть <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>
===Псевдокод=Решение за время <tex>O(nk)</tex>==
Пусть <tex>S</tex> — множество из <tex>n</tex> элементов, тогда для генерации случайного сочетания сделаем следующее:
* '''Шаг 1.''' Выберем в множестве случайный элемент,
* '''Шаг 2.''' Добавим его в сочетание,
* '''Шаг 3.''' Удалим элемент из множества.
Эту процедуру необходимо повторить <tex>k</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 = random(1, (n - 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
</code>
===Доказательство корректности алгоритма===
На первом шаге мы выбираем один элемент из <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>==
===Псевдокод===
*<tex>\mathtt{arrayOfElements}</tex> — массив, в котором находятся все элементы множества <tex>\mathtt{S}</tex>,*<tex>\mathtt{randomShuffle()}</tex> — функция генерации случайной перестановки.
<code>
'''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
</code>
===Доказательство корректности алгоритма===
Заметим, что всего перестановок <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>. То есть каждому сочетанию сопоставляется одна уникальная перестановка. Следовательно, генерация сочетания происходит также равновероятно.
===Оценка временной сложности===
== См. также ==
*[[Метод генерации случайной перестановки, алгоритм Фишера-ЙетсаПолучение номера по объекту|Получение номера по объекту]]*[[Генерация комбинаторных объектов в лексикографическом порядке]]
== Источники информации ==
*[http://www.rsdn.ru/article/alg/Combine.xml#ECPAC RSDN - Герасимов В. А. — Генерация случайных сочетаний. Генерация сочетания по его порядковому номеру]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]