0
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ " distance between integers with the same bit set count ... is nearly consecutive " sounds confusing to me. You mean that the binary numbers with a given fixed weight are approximately equispaced, no? $\endgroup$ – leonbloy Apr 1 '19 at 17:07
  • $\begingroup$ Why not just sort the integers by their bit counts? A run of consecutive elements in a list is certainly equally spaced. $\endgroup$ – Greg Martin Apr 1 '19 at 17:08
  • $\begingroup$ @GregMartin that is a good point. Your suggestion is the trivial case. I need to modify my questions to be more specific where the integers of the same bit set count are not grouped together, but are also spread equally across the entire list with maximum spacing. $\endgroup$ – linuxfreebird Apr 1 '19 at 17:11
  • $\begingroup$ @leonbloy I am unsure of what you are asking me. Do you want me to define set bit count as a fixed weight? $\endgroup$ – linuxfreebird Apr 1 '19 at 17:16
0
$\begingroup$

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.

$\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.