Методы генерации случайного сочетания — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Решение за время O(nk))
Строка 43: Строка 43:
  
  
*<tex>arrayOfElements</tex> — массив в котором находятся все элементы множества <tex>C</tex>,
+
*<tex>arrayOfElements</tex> — массив, в котором находятся все элементы множества <tex>C</tex>,
 
*<tex>exist</tex> — такой массив, что если <tex>exist[i] == 1</tex>, то <tex>i</tex> элемент присутствует в множестве <tex>S</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>\mathrm{random(1, i)}</tex> генерирует случайное число в интервале <tex> [1;\; i] </tex>.

Версия 18:17, 16 декабря 2014

Задача:
Необходимо сгенерировать случайное сочетание из [math] n [/math] элементов по [math] k [/math] с равномерным распределением вероятности, если есть в наличии функция для генерации случайного числа в заданном интервале.


Наивное решение

Пусть [math]S[/math] — массив из [math]n[/math] элементов, тогда для генерации случайного сочетания сделаем следующее:

  • запишем в массив [math]C[/math] числа от [math]1[/math] до [math]k[/math],
  • выберем случайные номер сочетания [math]r[/math],
  • применим алгоритм генерации следующего сочетания [math]r - 1[/math] раз к массиву [math]C[/math],
  • в [math]C[/math] хранятся номера позиции из [math]S[/math] входящих в случайное сочетание, запишем в [math]C[/math] эти элементы.


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


Псевдокод

 int[] randomCombination(int[] S, int n, int k)
   sort(S);
   for i = 1 to k 
     C[i] = i
   r = random(1, n! / (k!(n - k)!))
   for i = 1 to r - 1
     next_Combination(C, n, k)
   for i = 1 to k
     C[i] = S[C[i]]
   return C

Сложность алгоритма — [math]O(nr)[/math].

Решение за время [math]O(nk)[/math]

Пусть [math]S[/math] — множество из [math]n[/math] элементов, тогда для генерации случайного сочетания сделаем следующее:

  • выберем в множестве случайный элемент,
  • добавим его в сочетание,
  • удалим элемент из множества.

Эту процедуру необходимо повторить [math]k[/math] раз.


  • [math]arrayOfElements[/math] — массив, в котором находятся все элементы множества [math]C[/math],
  • [math]exist[/math] — такой массив, что если [math]exist[i] == 1[/math], то [math]i[/math] элемент присутствует в множестве [math]S[/math],
  • [math]\mathrm{random(1, i)}[/math] генерирует случайное число в интервале [math] [1;\; i] [/math].

Псевдокод

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++;
        if cur == r
          res[i] = arrayOfElements[j]
          exist[j] = false
  sort(res)
  return res

Доказательство корректности алгоритма

На первом шаге мы выбираем один элемент из [math]n[/math], на втором из [math]n - 1[/math], ..., на [math]k[/math]-ом из [math]n - k + 1[/math]. Тогда общее число исходов получится [math]n \cdot (n - 1) \cdot ... \cdot (n - k + 1)[/math]. Это эквивалентно [math]{n! \over (n - k)!}[/math]. Однако заметим, что на этом шаге у нас получаются лишь размещения из [math]n[/math] по [math]k[/math]. Но все эти размещения можно сопоставить одному сочетанию, отсортировав их. И так как размещения равновероятны, и каждому сочетанию сопоставлено ровно [math]k![/math] размещений, то сочетания тоже генерируются равновероятно.

Решение за время [math]O(n)[/math]

Для более быстрого решения данной задачи воспользуемся следующим алгоритмом: пусть задан для определенности массив [math]a[/math] размера [math]n[/math], состоящий из [math]k[/math] единиц и [math]n - k[/math] нулей. Применим к нему алгоритм генерации случайной перестановки. Тогда все элементы [math]i[/math], для которых [math]a[i] = 1[/math], включим в сочетание.

  • [math]arrayOfElements[/math] — массив в котором находятся все элементы множества [math]C[/math],
  • [math]randomShuffle()[/math] — функция генерации случайной перестановки.

Псевдокод

 int[] randomCombination(int[] arrayOfElements, int n, int k)
   for i = 1 to n 
     if i <= k
       a[i] = 1
     else
       a[i] = 0
   randomShuffle(a)
   for i = 1 to n
     if a[i] == 1
       ans.push(arrayOfElement[i])
   return ans

Доказательство корректности алгоритма

Заметим, что всего перестановок [math]n![/math], но так как наш массив состоит только из [math]0[/math] и [math]1[/math], то перестановка только [math]0[/math] или только [math]1[/math] ничего в нем не меняет. Заметим, что число перестановок нулей равно [math](n - k)![/math], единиц — [math]k![/math]. Следовательно, всего уникальных перестановок — [math]{n! \over k!(n - k)!}[/math]. Все они равновероятны, так как была сгенерирована случайная перестановка, а каждой уникальной перестановке сопоставлено ровно [math]k!(n - k)![/math] перестановок. Но [math]{n! \over k!(n - k)!}[/math] — число сочетаний из [math]n[/math] по [math]k[/math]. То есть каждому сочетанию сопоставляется одна уникальная перестановка. Следовательно, генерация сочетания происходит также равновероятно.

Оценка временной сложности

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

См. также

Источники информации