Изменения

Перейти к: навигация, поиск

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

73 байта убрано, 16:53, 27 декабря 2012
Псевдокод
===Псевдокод===
randomCombination(arrayOfElements, n, k)
'''for''' i = 1 '''to''' k
r = rand(1..n - i + 1);
cur = 0;
'''for''' j = 1 '''to''' n
'''if''' exist[j]
cur++;
'''if''' cur == r
res[i] = arrayOfElements[j]
exist[j] = false;
sort(res);
return res;
'''for''' i = 1 '''to''' k r = rand(1..n - i + 1); cur = 0; '''for''' j = 1 '''to''' n '''if''' exist[j] cur++; '''if''' cur == r res[i] = a[j] exist[j] = false; sort(res); Здесь <tex>a[]</tex> — исходный массив элементов, <tex>res[]</tex> — массив, где будет находиться результат, <tex>exist[]</tex> — такой массив, что если <tex>exist[i] == 1</tex>, то <tex>i</tex> элемент присутствует в множестве S.
Сложность алгоритма — <tex>O(n^2)</tex>
34
правки

Навигация