C'è un teorema che si riferisce a calcolare il numero totale di un oggetto combinatorio con la raccolta di uno a caso?

Question

Una sfida algoritmica comune è quella di generare un oggetto di un certo tipo, uniformemente a caso. Ad esempio, generando un permutazione casuale di dimensioni $ k $ da un determinato set (multi) di $ N $ Caratteri, come in Questa domanda .

Ho notato che quando si risolve tali attività, qualsiasi algoritmo per calcolando il numero di tali oggetti combinatoriali tramite una relazione di ricorrenza può essere trasformato in un algoritmo a generare tali oggetti combinatoriali. La mia domanda è, c'è un nome per questa tecnica? C'è un teorema che dice quando è vero?

Ad esempio, Supponiamo che voglio generare una sequenza casuale di $ n $ $ 1 $ s e $ 0 $ s, dove non ci sono due due adiacenti $ 1 $ s. Posso iniziare lasciando $ A [n] $ essere il numero di tali sequenze e osservarlo $$ A [N]= A [N-1] + A [N-2]. $$

(questa è la relazione fibonacci.) Questo mi consente di calcolare in modo efficiente una tabella di $ a [i] $ per $ i= 1 $ a $ i= n $ . Ora se voglio generare una sequenza di tale casuale, tutto ciò che devo fare è:

Step 1: Genera un valore casuale $ r $ da $ 1 $ a $ A [n] $ .

Step 2: Utilizzare la relazione di ricorrenza per individuare un Sub-termine che corrisponde alla $ R $ Sequenza: .

se $ r \ le a [n-1] $ , trova ricorsivamente la $ R $ < / SPAN> TH sequenzia contato da $ A [n-1] $ e aggiungere una $ 0 $ .

altrimenti, se $ a [n-1] , impostato $ R '= R - A [N-1] $ , e trova ricorsivamente la $ R' $ La sequenza contati da $ A [n-2] $ e aggiungere una classe $ 01 $ .

Ciò che sembra andare avanti qui è quello, dato qualsiasi relazione di ricorrenza per $ A [n] $ , posso trasformarlo in un algoritmo ricorsivo che restituisce il $ R $ oggetto contato da $ a [n] $ . Suppongo che questo sia ben noto, quindi sarei interessato a qualsiasi riferimento o risultati classici su questo. In particolare, questo non è solo specifico per l'esempio $ A [n] $ , ma dovrebbe essere vero per qualsiasi relazioni di recidiva soddisfacente Proprietà.

Inoltre, penso che questo possa essere correlato ad alcune ricerche sui test casuali.

Answer 1

Questi sono noti come Classifica e funzioni Originanti .Hai ragione sulla corrispondenza tra i rapporti di recidiva per il conteggio e gli algoritmi annullanti.