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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Решение за время O(n ^ 2))
м (rollbackEdits.php mass rollback)
 
(не показано 69 промежуточных версий 4 участников)
Строка 1: Строка 1:
==Постановка задачи==
+
{{Задача
 +
|definition =  
 
Необходимо сгенерировать случайное сочетание из <tex> n </tex> элементов по <tex> k </tex> с равномерным распределением вероятности, если есть в наличии функция для генерации случайного числа в заданном интервале.
 
Необходимо сгенерировать случайное сочетание из <tex> n </tex> элементов по <tex> k </tex> с равномерным распределением вероятности, если есть в наличии функция для генерации случайного числа в заданном интервале.
 +
}}
  
==Решение за время <tex>O(n ^ 2)</tex>==
+
==Наивное решение==
  
 
Пусть <tex>S</tex>  —  множество из <tex>n</tex> элементов, тогда для генерации случайного сочетания сделаем следующее:
 
Пусть <tex>S</tex>  —  множество из <tex>n</tex> элементов, тогда для генерации случайного сочетания сделаем следующее:
* Выберем в множестве случайный элемент
+
* '''Шаг 1.''' Запишем в массив <tex>C</tex> числа от <tex>1</tex> до <tex>k</tex>,
* Добавим его в сочетание
+
* '''Шаг 2.''' Выберем случайный номер сочетания <tex>r</tex>,
* Удалим элемент из множества
+
* '''Шаг 3.''' Применим алгоритм [[Получение следующего объекта|получение следующего сочетания]] <tex>r - 1</tex> раз к массиву <tex>C</tex>,
 +
* '''Шаг 4.''' В <tex>C</tex> хранятся номера позиции из <tex>S</tex> входящих в случайное сочетание, запишем в <tex>C</tex> эти элементы.
 +
===Псевдокод===
 +
*<tex>\mathtt{arrayOfElements}</tex> — массив, в котором находятся все элементы множества <tex>\mathtt{S}</tex>.
 +
<code>
 +
  '''int[]''' randomCombination('''int[]''' arrayOfElements, '''int''' n, '''int''' k):
 +
    '''for''' i = 1 '''to''' k
 +
      C[i] = i
 +
    r = random(1, n! / (k!(n - k)!))    <font color=darkgreen> //random(1, i) генерирует случайное целое число в интервале [1..i]</font color=darkgreen>
 +
    '''for''' i = 1 '''to''' r - 1
 +
      nextCombination(C, n, k)          <font color=darkgreen> //nextCombination(C, n, k) генерирует следующие сочетание</font color=darkgreen>
 +
    '''for''' i = 1 '''to''' k
 +
      C[i] = arrayOfElements[C[i]]
 +
    '''return''' C
 +
</code>
 +
 
 +
Сложность алгоритма — <tex dpi="150">O({n! \over k!(n - k)!} \cdot n)</tex>.
 +
 
 +
==Решение за время <tex>O(nk)</tex>==
 +
 
 +
Пусть <tex>S</tex>  —  множество из <tex>n</tex> элементов, тогда для генерации случайного сочетания сделаем следующее:
 +
* '''Шаг 1.''' Выберем в множестве случайный элемент,
 +
* '''Шаг 2.''' Добавим его в сочетание,
 +
* '''Шаг 3.''' Удалим элемент из множества.
  
 
Эту процедуру необходимо повторить <tex>k</tex> раз.
 
Эту процедуру необходимо повторить <tex>k</tex> раз.
 
 
===Псевдокод===
 
===Псевдокод===
  randomCombination(arrayOfElements, n, k)
+
*<tex>\mathtt{arrayOfElements}</tex> — массив, в котором находятся все элементы множества <tex>\mathtt{S}</tex>,
 +
*<tex>\mathtt{exist}</tex> — такой массив, что если <tex>\mathtt{exist[i] == 1}</tex>, то <tex>\mathtt{i}</tex> элемент присутствует в множестве <tex>\mathtt{S}</tex>,
 +
<code>
 +
  '''int[]''' randomCombination('''int[]''' arrayOfElements, '''int''' n, '''int''' k):
 
   '''for''' i = 1 '''to''' k  
 
   '''for''' i = 1 '''to''' k  
     r = rand(1..(n - i + 1));
+
     r = random(1, (n - i + 1))              
     cur = 0;
+
     cur = 0
 
     '''for''' j = 1 '''to''' n  
 
     '''for''' j = 1 '''to''' n  
 
       '''if''' exist[j]
 
       '''if''' exist[j]
         cur++;
+
         cur = cur + 1
 
         '''if''' cur == r
 
         '''if''' cur == r
           res[i] = arrayOfElements[j];
+
           res[i] = arrayOfElements[j]
           exist[j] = false;
+
           exist[j] = false
   sort(res);
+
   sort(res)
   '''return''' res;
+
   '''return''' res
 
+
</code>
Здесь <tex>exist</tex> — такой массив, что если <tex>exist[i] == 1</tex>, то <tex>i</tex> элемент присутствует в множестве <tex>S</tex>.
 
 
 
Сложность алгоритма  —  <tex>O(n^2)</tex>
 
  
 
===Доказательство корректности алгоритма===
 
===Доказательство корректности алгоритма===
На первом шаге мы выбираем один элемент из <tex>n</tex>, на втором из <tex>n - 1</tex>, ..., на <tex>k</tex>-ом из <tex>n - k + 1</tex>. Тогда общее число исходов получится <tex>n \cdot (n - 1) \cdot ... \cdot (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>\dots</tex>  на <tex>k</tex>-ом из <tex>n - k + 1</tex>. Тогда общее число исходов получится <tex>n \times (n - 1) \times \dots \times (n - k + 1)</tex>. Это эквивалентно <tex dpi="180">{n! \over (n - k)!}</tex>. Однако заметим, что на этом шаге у нас получаются лишь размещения из <tex>n</tex> по <tex>k</tex>. Но все эти размещения можно сопоставить одному сочетанию, отсортировав их. И так как размещения равновероятны, и каждому сочетанию сопоставлено ровно <tex>k!</tex> размещений, то сочетания тоже генерируются равновероятно.
  
 
==Решение за время <tex>O(n)</tex>==
 
==Решение за время <tex>O(n)</tex>==
  
 
Для более быстрого решения данной задачи воспользуемся следующим алгоритмом: пусть задан для определенности массив <tex>a</tex> размера <tex>n</tex>, состоящий из <tex>k</tex> единиц и <tex>n - k</tex> нулей. Применим к нему [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса|алгоритм генерации случайной перестановки]]. Тогда все элементы <tex>i</tex>, для которых <tex>a[i] = 1</tex>, включим в сочетание.
 
Для более быстрого решения данной задачи воспользуемся следующим алгоритмом: пусть задан для определенности массив <tex>a</tex> размера <tex>n</tex>, состоящий из <tex>k</tex> единиц и <tex>n - k</tex> нулей. Применим к нему [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса|алгоритм генерации случайной перестановки]]. Тогда все элементы <tex>i</tex>, для которых <tex>a[i] = 1</tex>, включим в сочетание.
 
 
===Псевдокод===
 
===Псевдокод===
 
+
*<tex>\mathtt{arrayOfElements}</tex> — массив, в котором находятся все элементы множества <tex>\mathtt{S}</tex>,
 +
*<tex>\mathtt{randomShuffle()}</tex> — функция генерации случайной перестановки.
 
<code>
 
<code>
   randomCombination(arrayOfElements, n, k)
+
   '''int[]''' randomCombination('''int[]''' arrayOfElements, '''int''' n, '''int''' k):
 
     '''for''' i = 1 '''to''' n  
 
     '''for''' i = 1 '''to''' n  
 
       '''if''' i <= k
 
       '''if''' i <= k
         a[i] = 1;
+
         a[i] = 1
 
       '''else'''
 
       '''else'''
         a[i] = 0;
+
         a[i] = 0
     random_shuffle(a);
+
     randomShuffle(a)                       <font color=darkgreen> //randomShuffle() — функция генерации случайной перестановки</font color=darkgreen>
 
     '''for''' i = 1 '''to''' n
 
     '''for''' i = 1 '''to''' n
 
       '''if''' a[i] == 1
 
       '''if''' a[i] == 1
         ans.push(arrayOfElement[i]);
+
         ans.push(arrayOfElement[i])
     '''return''' ans;
+
     '''return''' ans
 
</code>
 
</code>
  
Строка 57: Строка 81:
 
===Оценка временной сложности===
 
===Оценка временной сложности===
  
Алгоритм состоит из 2 невложенных циклов по <tex>n</tex> итераций каждый и функции генерации случайной перестановки <tex>random\_shuffle()</tex>, работающей за <tex>O(n)</tex> по алгоритму [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса|Фишера—Йетcа]]. Следовательно, сложность и всего алгоритма <tex>O(n)</tex>
+
Алгоритм состоит из двух невложенных циклов по <tex>n</tex> итераций каждый и функции генерации случайной перестановки <tex>\mathrm{randomShuffle()}</tex>, работающей за <tex>O(n)</tex> по алгоритму [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса|Фишера—Йетcа]]. Следовательно, сложность и всего алгоритма <tex>O(n)</tex>
  
 
== См. также ==
 
== См. также ==
  
*[[Метод генерации случайной перестановки, алгоритм Фишера-Йетса]]
+
*[[Получение номера по объекту|Получение номера по объекту]]
 +
*[[Генерация комбинаторных объектов в лексикографическом порядке]]
  
== Источники ==
+
== Источники информации ==
  
*[http://www.rsdn.ru/article/alg/Combine.xml Герасимов В. А. - Генерация случайных сочетаний. Генерация сочетания по его порядковому номеру]
+
*[http://www.rsdn.ru/article/alg/Combine.xml Герасимов В. А. Генерация случайных сочетаний. Генерация сочетания по его порядковому номеру]
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Комбинаторика]]
 
[[Категория: Комбинаторика]]

Текущая версия на 19:35, 4 сентября 2022

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


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

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

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

Псевдокод

  • [math]\mathtt{arrayOfElements}[/math] — массив, в котором находятся все элементы множества [math]\mathtt{S}[/math].

 int[] randomCombination(int[] arrayOfElements, int n, int k):
   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] = arrayOfElements[C[i]]
   return C

Сложность алгоритма — [math]O({n! \over k!(n - k)!} \cdot n)[/math].

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

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

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

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

Псевдокод

  • [math]\mathtt{arrayOfElements}[/math] — массив, в котором находятся все элементы множества [math]\mathtt{S}[/math],
  • [math]\mathtt{exist}[/math] — такой массив, что если [math]\mathtt{exist[i] == 1}[/math], то [math]\mathtt{i}[/math] элемент присутствует в множестве [math]\mathtt{S}[/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 = cur + 1
        if cur == r
          res[i] = arrayOfElements[j]
          exist[j] = false
  sort(res)
  return res

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

На первом шаге мы выбираем один элемент из [math]n[/math], на втором из [math]n - 1[/math] [math]\dots[/math] на [math]k[/math]-ом из [math]n - k + 1[/math]. Тогда общее число исходов получится [math]n \times (n - 1) \times \dots \times (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]\mathtt{arrayOfElements}[/math] — массив, в котором находятся все элементы множества [math]\mathtt{S}[/math],
  • [math]\mathtt{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)                        //randomShuffle() — функция генерации случайной перестановки
   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]. То есть каждому сочетанию сопоставляется одна уникальная перестановка. Следовательно, генерация сочетания происходит также равновероятно.

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

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

См. также

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