3622
правки
Изменения
м
next_CombinationnextCombination(C, n, k) <font color=darkgreen> //nextCombination(C, n, k) генерирует следующие сочетание</font color=darkgreen>
*<tex>arrayOfElements</tex> — массив в котором находятся все элементы множества <tex>C</tex>,
*<tex>exist</tex> — такой массив, что если <tex>exist[i] == 1</tex>, то <tex>i</tex> элемент присутствует в множестве <tex>S</tex>,
*<tex>\mathrm{random(1..i)}</tex> генерирует случайное число в интервале <tex> [1;\; i] </tex>.
*<tex>arrayOfElements</tex> — массив в котором находятся все элементы множества <tex>C</tex>,
*<tex>randomShuffle()</tex> — функция генерации случайной перестановки,
*<tex>\mathrm{random(1..i)}</tex> генерирует случайное число в интервале <tex> [1;\; i] </tex>.
→Оценка временной сложности
==Наивное решение==
Пусть <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> эти элементы. <br/>*<tex>\mathrm{random(1..i)}</tex> генерирует случайное число в интервале <tex> [1;\; i] </tex> <br/>
===Псевдокод===
*<tex>\mathtt{arrayOfElements}</tex> — массив, в котором находятся все элементы множества <tex>\mathtt{S}</tex>.
<code>
'''int[]''' randomCombination('''int[]''' SarrayOfElements, '''int''' n, '''int''' k) sort(S);:
'''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
'''for''' i = 1 '''to''' k
C[i] = SarrayOfElements[C[i]]
'''return''' C
</code>
Сложность алгоритма — <tex dpi="150">O({n! \over k!(n - k)!} \cdot n)</tex>.
==Решение за время <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]
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 \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):
'''for''' i = 1 '''to''' n
'''if''' i <= k
'''else'''
a[i] = 0
randomShuffle(a) <font color=darkgreen> //randomShuffle() — функция генерации случайной перестановки</font color=darkgreen>
'''for''' i = 1 '''to''' n
'''if''' a[i] == 1
===Оценка временной сложности===
Алгоритм состоит из 2 двух невложенных циклов по <tex>n</tex> итераций каждый и функции генерации случайной перестановки <tex>\mathrm{randomShuffle()}</tex>, работающей за <tex>O(n)</tex> по алгоритму [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса|Фишера—Йетcа]]. Следовательно, сложность и всего алгоритма <tex>O(n)</tex>
== См. также ==
