Изменения

Пусть <tex>S</tex> — массив множество из <tex>n</tex> элементов, тогда для генерации случайного сочетания сделаем следующее:* отсортируем <tex>S</tex>,* запишем '''Шаг 1.''' Запишем в массив <tex>C</tex> первые числа от <tex>k1</tex> элементов до <tex>Sk</tex>,* выберем случайные '''Шаг 2.''' Выберем случайный номер сочетания <tex>r</tex>,* применим '''Шаг 3.''' Применим алгоритм генерации [[Получение следующего объекта|получение следующего сочетания ]] <tex>r - 1</tex> раз к массиву <tex>C</tex>,* '''Шаг 4. ''' В <tex>C<br/tex>*хранятся номера позиции из <tex>\mathrm{random(1..i)}S</tex> генерирует входящих в случайное число сочетание, запишем в интервале <tex> [1;\; i] C</tex> <br/>эти элементы.

'''int[]''' randomCombination('''int[]''' SarrayOfElements, '''int''' n, '''int''' k) sort(S);:

C[i] = S[i] r = random(1, n! / (k!(n - k)!)) <font color=darkgreen> //random(1, i) генерирует случайное целое число в интервале [1..i]</font color=darkgreen>

next_CombinationnextCombination(C, n, k) <font color=darkgreen> //nextCombination(C, n, k) генерирует следующие сочетание</font color=darkgreen> '''for''' i = 1 '''to''' k C[i] = arrayOfElements[C[i]] '''return''' resC

Сложность алгоритма — <tex dpi="150">O({n! \over k!(n - k)!} \cdot n)</tex>. ==Решение за время <tex>O(n ^ 2nk)</tex>==

* выберем '''Шаг 1.''' Выберем в множестве случайный элемент,* добавим '''Шаг 2.''' Добавим его в сочетание,* удалим '''Шаг 3.''' Удалим элемент из множества.

*<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):

r = randrandom(1.., (n - i + 1))

cur = cur++;1

 Здесь <tex>exist</tex> — такой массив, что если <tex>exist[i] == 1</tex>, то <tex>i</tex> элемент присутствует в множестве <tex>S</tex>. Сложность алгоритма — <tex>O(n^2)</texcode>

На первом шаге мы выбираем один элемент из <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> размещений, то сочетания тоже генерируются равновероятно.

'''int[]''' randomCombination('''int[]''' arrayOfElements, '''int''' n, '''int''' k):

random_shufflerandomShuffle(a) <font color=darkgreen> //randomShuffle() — функция генерации случайной перестановки</font color=darkgreen>

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