0

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.

Bernard
  • 175,478
linuxfreebird
  • 557
  • 2
  • 11
  • " 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? – leonbloy Apr 01 '19 at 17:07
  • Why not just sort the integers by their bit counts? A run of consecutive elements in a list is certainly equally spaced. – Greg Martin Apr 01 '19 at 17:08
  • @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. – linuxfreebird Apr 01 '19 at 17:11
  • @leonbloy I am unsure of what you are asking me. Do you want me to define set bit count as a fixed weight? – linuxfreebird Apr 01 '19 at 17:16

1 Answers1

1

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.

Ross Millikan
  • 374,822