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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Оценка временной сложности)
(Доказательство корректности алгоритма)
Строка 51: Строка 51:
  
 
===Доказательство корректности алгоритма===
 
===Доказательство корректности алгоритма===
 
+
Заметим, что всего перестановок <tex>n!</tex>, но так как наш массив состоит только из 0 и 1, то перестановка только 0 или только 1 ничего в нем не меняет. Заметим, что число перестановок нулей - <tex>(n - k)!</tex>, единиц - <tex>k!</tex>. Следовательно всего уникальных перестановок - <tex dpi = "180">{n! \over k!(n - k)!}</tex>. Все они равновероятны, так как содержат одинаковое количество равновероятных элементарных исходов. Но <tex dpi = "180">{n! \over k!(n - k)!}</tex> - число сочетание из <tex>n</tex> по <tex>k</tex>. То есть каждому сочетанию сопоставляется одна уникальная перестановка. Следовательно, генерация сочетания происходит также равновероятно.
 
 
  
 
===Оценка временной сложности===
 
===Оценка временной сложности===

Версия 10:01, 27 декабря 2012

Постановка задачи

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

Решение за время O(n2)

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

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

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

Псевдокод

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);

Здесь [math]a[][/math] - исходный массив элементов, [math]res[/math] - массив, где будет находиться результат, [math]exist[][/math] - такой массив, что если [math]exist[i] == 1[/math], то [math]i[/math] элемент присутствует в множестве S.

Сложность алгоритма - [math]O(n^2)[/math]

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

Решение за время O(n)

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

Псевдокод

 for i = 1 to n 
   if i <= k
     a[i] = 1;
   else
     a[i] = 0;
 random_shuffle(a);
 for i = 1 to n
   if a[i] == 1
     insertInAnswer(i);

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

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

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

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

См. также

Источники