creating a balanced gray code with digits of different parity I have some code that generates all combinations from something like this:
[the or a] and [angry or mad or furious] and [cat or feline]

to this:
the angry cat
the mad cat
the furious cat
the angry feline
the mad feline
the furious feline
a angry cat
a mad cat
a furious cat
a angry feline
a mad feline
a furious feline

The problem is that this cross product may become too large, in which case I would like to fairly sample as many combinations as possible in a given time limit.  This is very similar to balanced gray codes but the parity is not the same for each "digit".  
The obvious algorithms (e.g. Breadth-First search and Depth-First search) will oversample some combinations and completely ignore others which probabilistic sampling like monte-carlo will evenly sample all combinations very well but it cannot efficiently enumerate all combinations.  Does anyone know of any algorithm for solving this problem?

Say you have $n_i$ options for slot $i$. Find the total number $n=\prod_in_i$ of possibilities, and find the next higher prime $p$. Find a primitive root $a$ modulo $p$, and traverse its powers $a^k$ modulo $p$. Skip the very few cases where the residue is greater than $n$. In all other cases, subtract $1$, successively divide by the $n_i$ and use the remainders as indices for the options.
In your example $n=12$, $p=13$, and e.g. $6$ is a primitive root modulo $13$. Its powers are $6$, $10$, $8$, $9$, $2$, $12$, $7$, $3$, $5$, $4$, $11$, $1$. If we subtract $1$, then divide by $2$ and use the remainder to index $\{\text{the},\text{a}\}$, then divide by $3$ and use the remainder to index $\{\text{angry},\text{mad},\text{furious}\}$, and then use what's left to index $\{\text{cat},\text{feline}\}$, this yields the following enumeration:
a furious cat
a mad feline
a angry feline
the mad feline
a angry cat
a furious feline
the angry feline
the mad cat
the furious cat
a mad cat
the furious feline
the angry cat

