A common algorithmic challenge is to generate an object of a certain kind, uniformly at random. For example, generating a random permutation of size $k$ from a given (multi)set of $N$ characters, as in this question.

I've noticed that when solving such tasks, any algorithm for calculating the number of such combinatorial objects via a recurrence relation can be transformed into an algorithm to generate such combinatorial objects. My question is, is there a name for this technique? Is there a theorem which says when this is true?

For example, suppose I want to generate a random sequence of $n$ $1$s and $0$s, where there are no two adjacent $1$s. I can begin by letting $a[n]$ be the number of such sequences, and observe that $$ a[n] = a[n-1] + a[n-2]. $$

(This is the Fibonacci relation.) This allows me to efficiently calculate a table of $a[i]$ for $i = 1$ to $i = n$. Now if I want to generate a random such sequence, all I have to do is:

Step 1: Generate a random value $r$ from $1$ to $a[n]$.

Step 2: Use the recurrence relation to locate a sub-term which corresponds to the $r$th sequence:

  • If $r \le a[n-1]$, recursively find the $r$th sequence counted by $a[n-1]$, and append a $0$.

  • Otherwise, if $a[n-1] < r \le a[n-1] + a[n-2]$, set $r' = r - a[n-1]$, and recursively find the $r'$th sequence counted by $a[n-2]$, and append a $01$.

What seems to be going on here is that, given any recurrence relation for $a[n]$, I can transform this into a recursive algorithm which returns the $r$th object counted by $a[n]$. I'm assuming this is well-known, so I would be interested in any references or classic results about this. In particular, this isn't just specific to the example $a[n]$, but should be true for any recurrence relation satisfying certain properties.

Also, I think this may be related to some research on random testing.


These are known as ranking and unranking functions. You are right about the correspondence between recurrence relations for counting and unranking algorithms.


Your Answer

