Previously, we computed the Bit-Reversal Permutation where we found how the order of indices would be permuted. In that case, we received an input n which was the order of the permutation of the indices where the length was 2n. However, this time, we are given a string of length m = 2k for some k. Now we want to apply the permutation indices of order k to a string.
Task
Your goal is to create a function or program that given a string where the length is a power of 2, output the permutation of it using bit-reversal.
As an example, the string 'codegolf'
has length 8 which is a power of 2, that is 8 = 23. We learned in the previous challenge that the bit-reversal permutation of order 3 is [0, 4, 2, 6, 1, 5, 3, 7]
which means that we select the characters from the input string using that order of indices.
Input Output
0 1 2 3 4 5 6 7 0 4 2 6 1 5 3 7
c o d e g o l f c g d l o o e f
This is one possible method of solving this task. Since we do not require the order of indices as output, there may be shorter algorithms which avoid generating the indices and rely on permuting characters only.
Test Cases
Input = Output
"z" = "z"
"cg" = "cg"
"code" = "cdoe"
"golf" = "glof"
"codegolf" = "cgdlooef"
"aaaazzzz" = "azazazaz"
"LynngDaie dneers" = "Legendary Dennis"
"hieroglyphically" = "hpoaeillihglrcyy"
"Programming Puzzles N' Code-Golf" = "PliorNPGosgem zlrenda'uog -mCzf"
"super spectacular dazzling dream" = "srenrzcrpdt sllau cg zueeaadpiam"
Rules
- This is code-golf so the shortest code wins.
- Builtins are allowed.
- The input string will only be in ASCII. The length of the input string will always be a power of 2.