1
$\begingroup$

Consider the unit hypercube in $\mathbb{R}^n$ with all non-negative coordinates, and one point anchored at $0^n$.

I've been working on a problem where I want to generate the (exponentially many) corners of this cube (as a list of 0's and 1's) but I want to generate them in "distance" order. That is starting from a corner (0,0,0...) I will generate a sequence of points $p_0, p_1 ... $ with the property that the distance of each point $p_k$ from the origin $p_0$ is either constant or increasing. (Naturally this means (1,1,...) will be the very last point in the sequence) and you can visualize this as "snaking around the cube".

To be more explicit in $\mathbb{R}^3$, a sample list I could generate would be:

$$\begin{pmatrix} 0,0,0 \\\ 1,0,0 \\\ 0,1,0 \\\ 0,0,1 \\\ 1,1,0 \\\ 1,0,1 \\\ 1,1,0 \\\ 1,1,1 \end{pmatrix} $$

This is not the ONLY solution. For any two entries $e_i$, $e_j$ if the number of "1"'s in the entries is equal, then a new list could be generated by "swapping" the entries in the original list.

My Work So Far:

A very inefficient solution:

I could generate the list of all binary numbers from $0$ to $2^{n} - 1$ with $n$ digits and then attempt to sort them by assigning an "magnitude" function that simply counts the number of "1's". This is very expensive especially given the exponential size of the data set and moreover cannot be done in a "batch" or online manner.

A slightly better solution:

For a positive integer $n$ and dimension $d$ define the following

Generator($n$, $d$)

if $n == 0$ then we return a vector of $d$ 0's.

If $n > 0$ then we consider the partially formed lists L_1 = $(1)$, L_2= $(0,1)$ , L_3 = $(0,0,1)$ ... $(0,0,0...1)$

Then we calculate Generator($n-1$, $d-r$) where r ranges from 1 to the length of L_max, and for each r we append to it the prefix list L_r.

Then calling Generator(0,n), Generator(1,n) ... Generator(n,n), as if it were one continuous list would yield our distance order tour of the cube.

$\endgroup$
3
$\begingroup$

For all $k=1, \dots, n$, you can easily generate all bit strings of length $n$ with exactly $k$ bits set.

The lexicographically smallest bit string has the $k$ ones in the $k$ least significant bits. If you interpret this string string as an integer, and it fits in a constant number of words, you can use bit tricks to find the next string in a constant number of operations.

See the section "Compute the lexicographically next bit permutation" here, and this answer for an explanation.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Here is a small snippet demonstrating the idea. $\endgroup$ – Steven Apr 7 at 21:31

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.