There are 2^n strings of length n comprising of only 1's and 2's. These strings can be listed such that successive strings differ in only one position. Such an ordering is called a Gray Code. The wikipedia article on Gray Codes has many examples.

There are k^n strings of length n where characters of the string are drawn from the alphabet {1, 2, 3, ..., k}. These strings can also be listed in Gray Code order. Instead of listing all strings in a Gray Code in their entirety, it suffices to list the starting string and differences in successive strings in O(1) time. This way, the overall time taken is proportional to n (the length of each string) and to the total number of strings in the Gray Code (see "Efficient generation of the binary reflected gray code and its applications" by J R Bitner, G Ehrlich & E M Reingold, CACM Vol 19, Issue 9, Sep 1976, p 517-521).

The number of strings of length n comprising of only 1's and 2's such that 22 is not a substring, equals a Fibonacci number. Interestingly, these strings can also be listed in Gray Code order so that successive strings differ in exactly one position. There exist "loopless" algorithms for the problem (that produce differences between successive strings in O(1) time).

In the course of a research paper (A Loopless Gray Code for Minimal Signed-Binary Representations by G S Manku and J Sawada, Proc. 13th Annual European Symposium on Algorithms (ESA 2005), p 438--447, Oct 2005), we encountered the problem of generating strings of length k such that the i-th character is drawn from the alphabet {1, 2, 3, ..., t[i]}, with t[i] ≥1. The strings are restricted as follows: if the i-th character is t[i], then the (i-1)-th character must be 1. For the special case where all t[i] = 2, the definition degenerates into Fibonacci strings, as defined above (strings without 22 as a substring). It is possible to enumerate these strings in Gray Code order with O(1) per string. We call the algorithm "Restricted Binary Reflected Gray Code (Restricted BRGC)".

Source code: brgc_restrict.c