Dgdrxrt

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

For example given $mathcalS_3=000_2,001_2,010_2,011_2,100_2,101_2,110_2,111_2$ in binary form, let $textbitcnt()$ count the number of set bits, then $textbitcnt(mathcalS_3)=0,1,1,2,1,2,2,3$. One could construct $mathcalD_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.

If $n$ is even, there are $n choose n/2=frac n!(n/2)!^2approx frac 2^nsqrtpi 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.