1632
правки
Изменения
м
===Псевдокод===
===Псевдокод===
rollbackEdits.php mass rollback
==Наивное решение==
Пусть <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[]''' SarrayOfElements, '''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] = SarrayOfElements[C[i]]
'''return''' C
</code>
Эту процедуру необходимо повторить <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)) <font color=darkgreen> //random(1, i) генерирует случайное число в интервале [1;\; i]</font color=darkgreen>
cur = 0
'''for''' j = 1 '''to''' n
===Доказательство корректности алгоритма===
На первом шаге мы выбираем один элемент из <tex>n</tex>, на втором из <tex>n - 1</tex>, ..., <tex>\dots</tex> на <tex>k</tex>-ом из <tex>n - k + 1</tex>. Тогда общее число исходов получится <tex>n \cdot times (n - 1) \cdot ... times \dots \cdot 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>a</tex> размера <tex>n</tex>, состоящий из <tex>k</tex> единиц и <tex>n - k</tex> нулей. Применим к нему [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса|алгоритм генерации случайной перестановки]]. Тогда все элементы <tex>i</tex>, для которых <tex>a[i] = 1</tex>, включим в сочетание.
===Псевдокод===
*<tex>\mathtt{arrayOfElements}</tex> — массив, в котором находятся все элементы множества <tex>\mathtt{S}</tex>,
*<tex>\mathtt{randomShuffle()}</tex> — функция генерации случайной перестановки.
<code>
'''int[]''' randomCombination('''int[]''' arrayOfElements, '''int''' n, '''int''' k):
===Оценка временной сложности===
Алгоритм состоит из 2 двух невложенных циклов по <tex>n</tex> итераций каждый и функции генерации случайной перестановки <tex>\mathrm{randomShuffle()}</tex>, работающей за <tex>O(n)</tex> по алгоритму [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса|Фишера—Йетcа]]. Следовательно, сложность и всего алгоритма <tex>O(n)</tex>
== См. также ==
