# 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?

## 2 Answers

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

• Do you know if there are any libraries that implement this in some programming language? – anthonybell Jul 6 '16 at 18:08
• @anthonybell: I don't. I could write you a Java class that does it. – joriki Jul 6 '16 at 18:09
• ok, thanks. I was just curious because I couldn't find anything earlier. Do you know if there are any kind of theoretical guarantees of randomness that can be said about enumerations generated with this method? – anthonybell Jul 6 '16 at 19:21
• @anthonybell: I don't, I made it up on the spot. – joriki Jul 6 '16 at 19:25

Here's a very similar approach to the answer by @joriki, which is in may ways simpler to implement (it requires neither primes nor the discovery of primitive roots), and which has been analyzed extensively:

As above, find $n=\prod_in_i$ and then find $m=2^{\lceil{log_2 n}\rceil}$. Finally, generate a random $a$ and $c$ such that $0<a,c<m, a\equiv1\pmod 4, c\equiv1\pmod2$. Then use a Linear Congruential Generator (LCG) starting with some randomly-selected $x_0$, producing at each step $x_{i+1} = a x_i + c\pmod m$. Skip over any values of $x_i$ which are greater than or equal to $m$ (which will be fewer than half the generated values) and converted the remaining ones to option sequences using a mixed-base representation.

The LCG produced in this way is guaranteed to cycle through all $m$ values, and for particular values of $a$ and $c$ could be used as a cheap pseudo-random number generator. It's performance as such has been analysed extensively. Not all values of $a$ are equally good; in general, you should use values somewhere in the vicinity of $\sqrt m$. One weakness of an LCG is that the low-order bits of successive entries are highly correlated. However, that will not bias the composition of a sample.