2
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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
$\endgroup$
  • $\begingroup$ Do you know if there are any libraries that implement this in some programming language? $\endgroup$ – anthonybell Jul 6 '16 at 18:08
  • $\begingroup$ @anthonybell: I don't. I could write you a Java class that does it. $\endgroup$ – joriki Jul 6 '16 at 18:09
  • $\begingroup$ 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? $\endgroup$ – anthonybell Jul 6 '16 at 19:21
  • $\begingroup$ @anthonybell: I don't, I made it up on the spot. $\endgroup$ – joriki Jul 6 '16 at 19:25
-1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.