Методы получения случайных комбинаторных объектов — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 9: Строка 9:
 
  '''object''' randomObject(n: '''int''', k: '''int'''):
 
  '''object''' randomObject(n: '''int''', k: '''int'''):
 
   '''for''' i = 1 '''to''' n                               
 
   '''for''' i = 1 '''to''' n                               
     s = number(prefix) <font color = green> // число комбинаторных объектор с текущим префиксом. </font>
+
     s = number(prefix) <font color = green> // число комбинаторных объектов с текущим префиксом. </font>
 
     r = random(1, s)
 
     r = random(1, s)
 
     '''for''' j = 1 '''to''' k   
 
     '''for''' j = 1 '''to''' k   

Версия 22:48, 7 декабря 2018

Описание алгоритма

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

Пусть [math] B = \{b_1, b_2 ..., b_k\} [/math] - множество различных элементов, которые могут находиться в данном комбинаторном объекте.

Будем получать элементы по порядку: сначала определим, какой элемент будет стоять на первом месте, потом на втором и так далее. Считаем, что мы построили префикс длинны [math] i [/math] : [math] I = \{a_1, a_2, \ldots, a_i\} [/math]. Будем выбирать элемент [math] a_{i+1} [/math] из множества всех возможных так, чтобы вероятность выбора элемнта [math] b \in B [/math], была пропорциональна числу комбинторных обьектов размера [math] n [/math] с префиксом [math] I + b [/math]. Для этого разобъем отрезок натуральных чисел [math] [1, s] [/math]. где [math] s [/math] - число различных комбинаторных объектов с текущим префиксом, на [math] k [/math] диапазонов так, чтобы размер диапазаоны [math] d_j [/math] был равен числу объектов с префиксом [math] I + b_j [/math]. С помощью функция для генерации случайного числа получим число [math] r [/math] в интервале [1, s] и добавим к префиксу [math] I [/math] элемент [math] b_j [/math] соответствующий диапазону отрезка в которм находится полученное число.

object randomObject(n: int, k: int):
  for i = 1 to n                               
    s = number(prefix)  // число комбинаторных объектов с текущим префиксом. 
    r = random(1, s)
    for j = 1 to k  
      if number(prefix + b[j]) < r 
        r = r - number(prefix + b[j])
      else 
        prefix[i] = b[j]
        break
  return prefix