Существует ли теорема, которая связывает вычисление общего числа комбинаторных объектов с выбором одного из них случайным образом?

Question

Обычная алгоритмическая задача состоит в том, чтобы сгенерировать объект определенного типа равномерно случайным образом.Например, генерация случайной перестановки размера $k$ из заданного (множественного) набора $N$ символы, как в этот вопрос.

Я заметил, что при решении таких задач любой алгоритм для вычисление количества таких комбинаторные объекты с помощью рекуррентного отношения могут быть преобразованы в алгоритм, позволяющий генерировать такие комбинаторные объекты.Мой вопрос в том, есть ли название для этой техники?Есть ли теорема, которая говорит, когда это верно?

Например, предположим, я хочу сгенерировать случайную последовательность $n$ $1$ы и $0$s, где нет двух смежных $1$s.Я могу начать с того, что позволю $a[n]$ быть числом таких последовательностей и наблюдать, что $$ a[n] = a[n-1] + a[n-2].$$

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

Шаг 1: Сгенерировать случайное значение $r$ От $1$ Для $a[n]$.

Шаг 2: Используйте рекуррентное соотношение, чтобы найти вспомогательный член, который соответствует $r$последовательность th:

• Если $r \le a[n-1]$, рекурсивно найти $r$- я последовательность , подсчитываемая по $a[n-1]$, и добавьте $0$.

• В противном случае, если $a[n-1] < r \le a[n-1] + a[n-2]$, установить $r' = r - a[n-1]$, и рекурсивно находим $r'$- я последовательность , подсчитываемая по $a[n-2]$, и добавьте $01$.

Что, по-видимому, здесь происходит, так это то, что, учитывая любое рекуррентное соотношение для $a[n]$, я могу преобразовать это в рекурсивный алгоритм , который возвращает $r$й объект, подсчитанный по $a[n]$.Я предполагаю, что это хорошо известно, поэтому мне были бы интересны любые ссылки или классические результаты по этому поводу.В частности, это относится не только к приведенному примеру $a[n]$, но должно быть истинным для Любой рекуррентное соотношение, удовлетворяющее определенным свойствам.

Кроме того, я думаю, что это может быть связано с некоторыми исследованиями по случайному тестированию.

Answer 1

Они известны как функции ранжирования и снятия рейтинга.Вы правы относительно соответствия между рекуррентными соотношениями для алгоритмов подсчета и снятия ранга.