Is there an ordering of integers with maximum near equal spacing between integers of the same set bit count?

72 Views Asked by At

Let $n$ be a whole number, and $\mathcal{S}_n$ be an ordered list of integers from 0 to $2^{n}-1$, does there exist an ordering $\mathcal{D}_n$ of $\mathcal{S}_n$ such that the distance between integers with the same bit set count in $\mathcal{D_n}$ is nearly consecutive (e.i. equal spaced), maximized, and the rules of constructing $\mathcal{D_n}$ are known?

For example given $\mathcal{S}_3=\{000_2,001_2,010_2,011_2,100_2,101_2,110_2,111_2\}$ in binary form, let $\text{bitcnt}()$ count the number of set bits, then $\text{bitcnt}(\mathcal{S}_3)=\{0,1,1,2,1,2,2,3\}$. One could construct $\mathcal{D}_3=\{000_2,111_2,001_2,110_2,010_2,101_2,100_2,011_2\}$ where pairs of integers are adjacent if they are set bit inverses of each other (e.i. ~$(000_2)=111_2$), which leads to consecutive spacing of integers with one set bit as $001_2-(1)-010_2-(1)-100_2$, and with two set bits $110_2-(1)-101_2-(1)-011_2$, where $a-(x)-b$ means $x$ integers are placed in between $a$ and $b$.

The trivial case of ordering by set bit count is by sorting all elements of set bit count, where all integers of the same bit set count are grouped together with zero spacing between them. The non-trivial case is when the spacing is maximum such that no two elements of the same bit set count are next to each other.

1

There are 1 best solutions below

0
On

If $n$ is even, there are ${n \choose n/2}=\frac {n!}{(n/2)!^2}\approx \frac {2^n}{\sqrt{\pi n/2}}$ with half the bits set. The best spacing you can get is then $\sqrt {\pi n/2}$ for those. For $n=20$ the exact value is $5.6$ so you can keep them $5$ positions apart. A simple approach is to scatter the numbers with half the bits set as evenly as possible, then put the ones with one extra bit set in the next locations and one less bit set in the previous locations. You can keep going with this spacing and will have room left for the ones farther from balanced.