Изменения

Методы генерации случайного сочетания

59 байт убрано, 19:26, 16 декабря 2014

Нет описания правки

* применим алгоритм генерации следующего сочетания <tex>r - 1</tex> раз к массиву <tex>C</tex>,

* в <tex>C</tex> хранятся номера позиции из <tex>S</tex> входящих в случайное сочетание, запишем в <tex>C</tex> эти элементы.

~~<br/>~~

*<tex>\mathrm{random(1, i)}</tex> генерирует случайное число в интервале <tex> [1;\; i] </tex>,

*<tex>\mathrm{nextCombination(C, n, k)}</tex> генерирует следующие сочетание.

~~<br/>~~

===Псевдокод===

'''for''' i = 1 '''to''' k

C[i] = i

r = random(1, n! / (k!(n - k)!)) //random(1, i) генерирует случайное число в интервале [1;\; i]

'''for''' i = 1 '''to''' r - 1

nextCombination(C, n, k) //nextCombination(C, n, k) генерирует следующие сочетание

'''for''' i = 1 '''to''' k

C[i] = S[C[i]]

*<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>.

===Псевдокод===

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

'''for''' i = 1 '''to''' k

r = random(1, (n - i + 1)) //random(1, i) генерирует случайное число в интервале [1;\; i]

cur = 0

'''for''' j = 1 '''to''' n

*<tex>arrayOfElements</tex> — массив, в котором находятся все элементы множества <tex>C</tex>,

*<tex>randomShuffle()</tex> — функция генерации случайной перестановки.

===Псевдокод===

'''else'''

a[i] = 0

randomShuffle(a) //randomShuffle() — функция генерации случайной перестановки

'''for''' i = 1 '''to''' n

'''if''' a[i] == 1

Анонимный участник