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

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.

meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.

Задача:

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

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

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

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

Псевдокод

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

 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

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

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

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

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

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

Псевдокод

• $\mathtt{arrayOfElements}$ — массив, в котором находятся все элементы множества $\mathtt{S}$,
• $\mathtt{exist}$ — такой массив, что если $\mathtt{exist[i] == 1}$, то $\mathtt{i}$ элемент присутствует в множестве $\mathtt{S}$,

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

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

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

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

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

Псевдокод

• $\mathtt{arrayOfElements}$ — массив, в котором находятся все элементы множества $\mathtt{S}$,
• $\mathtt{randomShuffle()}$ — функция генерации случайной перестановки.

 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

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

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

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

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

См. также

• Получение номера по объекту
• Генерация комбинаторных объектов в лексикографическом порядке

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

• Герасимов В. А. — Генерация случайных сочетаний. Генерация сочетания по его порядковому номеру