6
\$\begingroup\$

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 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.
\$\endgroup\$
  • 2
    \$\begingroup\$ This is a trivial modification of the previous question. \$\endgroup\$ – Peter Taylor Aug 4 '16 at 19:08
  • \$\begingroup\$ @PeterTaylor This is not a duplicate. The previous is asking for indices and this is asking to permute which means there might be more possible methods to solve it. Are challenges which ask for the number of cycles in a permutation a duplicate to challenges which ask for the cycles of a permutation? That is a trivial modification if any if you ask me. \$\endgroup\$ – miles Aug 4 '16 at 19:16
  • \$\begingroup\$ Yes, I would say they are. \$\endgroup\$ – Peter Taylor Aug 5 '16 at 6:10
  • \$\begingroup\$ @PeterTaylor We've had a challenge to generate the first n Fibonacci numbers and just recently we've had a challenge to find the product of the first n Fibonacci numbers. That is a trivial modification yet is a different task. Are you saying those are duplicates? \$\endgroup\$ – miles Aug 5 '16 at 6:24
  • \$\begingroup\$ This is not the place for extended discussions. If you want to discuss how non-trivial a modification must be to not be a dupe, take it to meta. \$\endgroup\$ – Peter Taylor Aug 5 '16 at 7:18
1
\$\begingroup\$

Pyth, 9 bytes

hu+M.Tc2G

Try it online

How it works

 u       Q   fixed point: let G = input, and repeatedly replace G with
      c2G      chop G into two equal pieces
    .T         justified transpose
  +M           map concatenate
             until a duplicate is found
h            take the first (only) element of the resulting list
\$\endgroup\$
1
\$\begingroup\$

Haskell, 72 bytes

This is "permuting characters only", but is it shorter than a different approach?

s(a:b:c)|(x,y)<-s c=(a:x,b:y)
s n=(n,n)
r a|[_]<-a=a|(x,y)<-s a=r x++r y

s is a helper function to seperate the characters from even and odd positions, r is the bit reversal permutation function:

Prelude> r "codegolf"
"cgdlooef"
\$\endgroup\$
1
\$\begingroup\$

Python 3.5, 112 111 bytes:

from math import*;lambda d:''.join([d[int(bin(i)[2:].zfill(int(log2(len(d))))[::-1],2)]for i in range(len(d))])

You really start to appreciate the all in one power and compactness of Python once you start using languages like C and Java. Anyways, this is an anonymous function that you call by first naming it, and then calling it like a normal function wrapped inside the print() function.

Try It Online! (Ideone)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.