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

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

Версия 20:27, 10 января 2013

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

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

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

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

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

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

Псевдокод

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;

Здесь [math]exist[][/math] — такой массив, что если [math]exist[i] == 1[/math], то [math]i[/math] элемент присутствует в множестве S.

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

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

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

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

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

Псевдокод

 randomCombination(arrayOfElements, n, k)
   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
       ans.push(arrayOfElement[i]);
   return ans;

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

Заметим, что всего перестановок [math]n![/math], но так как наш массив состоит только из 0 и 1, то перестановка только 0 или только 1 ничего в нем не меняет. Заметим, что число перестановок нулей равно [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]random\_shuffle()[/math], работающей за [math]O(n)[/math] по алгоритму Фишера—Йетcа. Следовательно, сложность и всего алгоритма [math]O(n)[/math]

См. также

Источники