Existe um teorema que relaciona o cálculo do número total de um objeto combinatório com a escolha de um aleatoriamente?

Question

Um desafio algorítmico comum é gerar um objeto de um certo tipo, uniformemente aleatoriamente. Por exemplo, gerando uma permutação aleatória de tamanho $ k $ de um determinado (multi) conjunto de $ n $ Caracteres, como em Esta questão .

Eu notei que, ao resolver essas tarefas, qualquer algoritmo para Calculando o número de objetos combinatórios de tal / em> por meio de uma relação de recorrência pode ser transformada em um algoritmo para gerar objetos combinatórios. Minha pergunta é, há um nome para esta técnica? Existe um teorema que diz quando isso é verdade?

por exemplo, suponha que eu quero gerar uma sequência aleatória de $ n $ $ 1 $ s e $ 0 $ s, onde não há dois adjacentes $ 1 $ s. Eu posso começar deixando $ a [n] $ ser o número de essas sequências e observar que $$ A [N]= A [N-1] + A [N-2]. $$

(esta é a relação de fibonacci.) Isso me permite calcular eficientemente uma tabela de $ a [i] $ para $ i= 1 $ para $ i= n $ . Agora, se eu quiser gerar uma sequência aleatória, tudo o que tenho a fazer é:

etapa 1: gerar um valor aleatório $ R $ de $ 1 $ para $ a [n] $ .

etapa 2: Use a relação de recorrência para localizar um sub-prazo que corresponde à $ R $ th seqüência:

• se $ r \ le a [N-1] $ , recursivamente encontrar a $ R $ < / span> th seqüência contada por $ a [N-1] $ e anexe uma $ 0 $ .

• Caso contrário, se $ a [N-1] , definido $ r '= r - a [n-1] $ e recursivamente encontrar a $ r' $ a sequência contada por $ a [N-2] $ e anexe uma $ 01 $ .

O que parece estar acontecendo aqui é que, dada qualquer relação de recorrência para $ a [n] $ , posso transformar isso em um algoritmo recursivo que retorna $ R $ th objeto contado por $ a [n] $ . Estou supondo que isso seja bem conhecido, então eu estaria interessado em quaisquer referências ou resultados clássicos sobre isso. Em particular, isso não é apenas específico para o exemplo $ a [n] $ , mas deve ser verdade para qualquer Relação de recorrência satisfatória Propriedades.

Além disso, acho que isso pode estar relacionado a algumas pesquisas em testes aleatórios.

Answer 1

Estes são conhecidos como Classificação e funções de ranking .Você está certo sobre a correspondência entre relações de recorrência para contagem e desanrosamento de algoritmos.