# How to efficiently sample a large number of unique binary vectors

This is probably just a basic CS question, so I appreciate the help. I'm doing Monte Carlo permutation tests in matlab for One-Sample and Paired Two-Sample Tests (where there are x^n unique vectors for n observations of x possible classes) and it is taking a very long time to generate all of the unique vectors.

For very large numbers of samples, the time it takes to generate that many unique vectors increases dramatically as the number of samples increases (for two reasons, one is the reduced ratio of unsample:sampled unique permutations and the second is the need to compare each new permutation to the previous permutations to see if it’s unique). I could speed things up immensely if I could pre-generate every possible subset and then just sample from the indices of those vectors, but obviously the size of the matrix of all possible vectors is too large.

Is there a way to turn an index into what would be the corresponding vector? It seems like there must be. I.e. in the binary case (x = 2), if each vector has 10 observations, there are 2^10 unique binary vectors. The random number generator delivers 512, so the program calculates the unique binary vector that corresponds to index 512 and returns that. That way I could just pull the desired number of indices from [1,2^10] and calculate the corresponding unique binary vector for each.

Eventually I’ll need to take that to the multiclass case (x>3) and for unpaired two-sample tests (where there are n! possible combinations of the observations), but the binary subset case seems like the easiest place to start.

Thought on how to do that? Again, thanks for the help.

• I think the de2bi function does exactly this for the x=2 case. But if anyone made it though that whole question and has thoughts on how to implement the x>2 or for n! case, I would love pointers on that. Thanks! – jim Aug 25 '16 at 5:58
• Please see the edit to my answer. – Kodiologist Aug 25 '16 at 15:06
• Why "unique"? I don’t think the vectors need to be unique. Monte Carlo is a sampling with replacement. – Elvis Aug 25 '16 at 15:10
• It's difficult to tell what the problem is. You cannot possibly generate all the unique vectors for anything other than a tiny problem, and for anything larger there are so many possibilities that it will be almost impossible to sample any vector more than once at random. It's unclear what binary vectors have to do with permutation tests (which by definition require permutations rather than subsets). – whuber Aug 25 '16 at 15:14

This seems to be equivalent to the question of how to convert a number to a binary numeral. So just use your favorite method for that (perhaps exploiting the fact that the number is probably already internally represented in binary) and interpret each bit as an element of the vector.

For more than two classes, increase the radix appropriately (e.g., for 4 classes, convert your numbers to base-4 numerals).

For the factorial case, where you want to sample from the $n!$ arrangements of $n$ objects, you might be best served with a Fisher-Yates shuffle.