Bit-Reversal Permutations
Haskell, 40 37 bytes
f 0=[0]
f a=[(*2),(+1).(*2)]<*>f(a-1)
Try it online!
Thanks to @Laikoni for three bytes!
05AB1E, 8 bytes
Code:
¾)IF·D>«
Explanation:
¾ # Constant for 0.
) # Wrap it up into an array.
IF # Do the following input times.
· # Double every element.
D # Duplicate it.
> # Increment by 1.
« # Concatenate the first array.
Uses the CP-1252 encoding. Try it online!.
J, 15 11 bytes
2&(*,1+*)0:
There is an alternative for 15 bytes that uses straight-forward binary conversion and reversal.
2|."1&.#:@i.@^]
Usage
f =: 2&(*,1+*)0:
f 0
0
f 1
0 1
f 2
0 2 1 3
f 3
0 4 2 6 1 5 3 7
f 4
0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15
Explanation
2&(*,1+*)0: Input: n
0: The constant 0
2&( ) Repeat n times starting with x = [0]
2 * Multiply each in x by 2
1+ Add 1 to each
, Append that to
2 * The list formed by multiplying each in x by 2
Return that as the next value of x
Return the final value of x