Reflective binary ordering

Question

The reverse of an n-bit number is just its n binary digits in reverse order:

001010010 → 010010100

Given a number n, generate all n-bit integers ([0, 2ⁿ-1]) in an arbitrary order, with only one restriction: there must be a splitting point such that the reverse of an integer is on the opposite side of the splitting point. Integers which are their own reverse must come before the splitting point.

Other than this single splitting point there are no restrictions, all the integers before or after it may come in whatever order you desire.

Example for 4 bits (you don't have to generate this order):

0000, 0001, 0010, 0011, 0101, 0110, 0111, 1001, 1011, 1111,
0100, 1000, 1010, 1100, 1101, 1110

You may output the integers as their binary digits or just as integers. You don't have to explicitly output the splitting point.

• user9206: Could you add the splitting point to your example?
• Greg Martin: To clarify: you want all the n-bit numbers to be partitioned into two subsets, with the property that a number and its reverse are always in different subsets (other than numbers that are their own reverses). Is that right?
• orlp: @Lembik It's already there: the newline.
• orlp: @GregMartin Correct.

Answer 1

JavaScript (ES6), (削除) 129 (削除ここまで) 114 bytes

f=n=>[...Array(p=1<<n)].map((_,i)=>(p+i).toString(2).slice(1)).sort((a,b)=>g(a)-g(b),g=a=>[...a].reverse().join``<a)

I appear to have stumbled on the code that happens to generate the given example for 4 bits. Edit: Saved 15 bytes thanks to @ConorO'Brien.

Answer 2

PHP, 80 Bytes

Make 2 Groups in a 2D Array

After the first Group is the splitting point

In the first group are the integers with their own reverse and the integers that are lower than their reverse

for(;$i<1<<$argn;)$r[strrev($b=sprintf("%0{$argn}b",$i++))<$b][]=$b;print_r($r);

Try it online!

PHP>=7.0, 82 Bytes

Make 3 Groups in a 2D Array

After the second Group is the splitting point

In the first group are the integers with their own reverse

In the second group are the integers that are lower than their reverse

Use the Spaceship Operator

for(;$i<2**$argn;)$r[strrev($b=sprintf("%0{$argn}b",$i++))<=>$b][]=$b;print_r($r);

Try it online!

Answer 3

Jelly, 13 bytes

2ṗ’μżUṢ€QZ;/Q

Try it online!

Group with their reflections, uniquify and sort, then zip.

Answer 4

Mathematica, 51 bytes (Windows ANSI encoding)

±n_:=SortBy[{0,1}~Tuples~n,(#-Reverse@#).Range@n!&]

Defines a unary function ± taking a positive integer argument and returning a list of lists of 0s and 1s. For example, ±4 returns

{{1, 1, 0, 0}, {1, 0, 0, 0}, {1, 1, 1, 0}, {1, 0, 1, 0}, {0, 1, 0, 0},
 {1, 1, 0, 1}, {0, 0, 0, 0}, {0, 1, 1, 0}, {1, 0, 0, 1}, {1, 1, 1, 1},
 {0, 0, 1, 0}, {1, 0, 1, 1}, {0, 1, 0, 1}, {0, 0, 0, 1}, {0, 1, 1, 1},
 {0, 0, 1, 1}}

SortBy[{0,1}~Tuples~n,...] takes the set of all length-n lists of 0s and 1s and sorts them according to the values that the function ... takes on each such list. It suffices to find a function whose values on a list and its reverse are negatives of each other and whose value is 0 only if the list is its own reverse. Taking the dot product of (the list minus its reverse) and (a sufficiently unbalanced vector, such as Range@n! which is {1!, 2!, ..., n!}) does the trick.

Answer 5

Pyth, 14 bytes

o&NcNijN2 .5^2

Try it online

How it works

Sort by x / f(x), where f(x₀⋅2⁰ + x₁⋅2¹ + x₂⋅2² + ...) = x₀⋅0.5⁰ + x₁⋅0.5¹ + x₂⋅0.5² + ... (for binary digits x_i ∈ {0, 1}). Interestingly, this same ordering works for all n, but with different splitting points. If x is less than or equal to its n bit reversal, then x / f(x) ≤ 2^{n − 1}, otherwise x / f(x)> 2^{n − 1}.

o ^2Q sort values [0, ..., 2**n-1] by this key:
 &N if value is 0, key is 0
 cN else, key is value divided by
 i .5 the base 0.5 number whose digits are
 j 2 the base 2 digits of
 N value