Reorder a string of length \2ドル^n\$ by permuting the \$n\$ binary digits of every index

Question

Given a binary string \$s\$ of length \2ドル^n\$ and a permutation \$\sigma\$ of \$\{1,\dots,n\}\$, generate the binary string \$u\$ of length \2ドル^n\$ which is a reordering of \$s\$ such that \$u[i^\sigma]=s[i]\$ for each (\0ドル\$-based) index \$i\$, where \$i^\sigma\$ is obtained by \$\sigma\$-reordering the \$n\$ binary digits of \$i\$.

For example, \110ドル_b^{(23)}=101_b\$, so if \$\sigma\$ is the transposition \$(23)\$ then we need u[5] == s[6].

Note: we can think of \$s\$ as the truth table of an \$n\$-ary truth function, \$\sigma\$ as a reordering of the truth function's inputs, and \$u\$ as the truth table resulting from this reordering.

Full example: n=3, s=11010010, σ=(123) \$\to\$ u=10011100, because each index \$i=xyz_b\$ in \$s\$ maps to index \$zxy_b\$ in \$u\$, so we have

u[000] = s[000] = 1
u[001] = s[010] = 0
u[010] = s[100] = 0
u[011] = s[110] = 1
u[100] = s[001] = 1
u[101] = s[011] = 1
u[110] = s[101] = 0
u[111] = s[111] = 0

You can use any reasonable representation for \$\sigma\$ (e.g. a list \$[\sigma(1),\dots,\sigma(n)]\$ or cycle notation) and for \$s\$ (e.g. a bytestring, bigint, or list of booleans) and any standard input/output convention.

• Unrelated String: Now I'm wondering about a related problem--given a permutation of \${1, ..., 2^n}\,ドル determining whether or not it corresponds to such a bit permutation! Actually, I suppose that should be as simple as transposing the bits of the indices and seeing if lexicographically sorting those gives \$[0, ..., 2^n - 1]\$.
• Karl: @UnrelatedString how about: given two bit strings of length \2ドル^n\,ドル determine whether they differ by a permutation of this form.
• Karl: Also related: math.stackexchange.com/questions/4974317

Answer 1

Python + NumPy, 45 bytes

-5 thanks @att

lambda a,p:a.reshape(p*0+2).transpose(p).flat

Attempt This Online!

Expects the binary string and the permutation as NumPy arrays and returns a NumPy flatiter object.

How?

Quite literal approach: Arranges the input sequence into a 2x2x...x2 hypercube, shuffles dimensions according to permutation, and flattens the result.

• att: if you're taking it as a numpy array 0*p+2

Answer 2

Charcoal, 16 bytes

⭆θ§θΣEη∧&κX2μX2λ

Try it online! Link is to verbose version of code. Takes s as the first input as a list or bitstring and σ as the second input as a list (or string if n<11) of 0-indexed destination indices and outputs a bitstring. Explanation:

 θ First input `s`
⭆ Map over characters and join
 θ First input `s`
 § Indexed by
 η Second input `σ`
 E Map over indices
 κ Outer index
 & Bitwise and
 2 Literal integer `2`
 X Raised to power
 μ Source index
 ∧ Logical And
 2 Literal integer `2`
 X Raised to power
 λ Destination index
 Σ Take the sum
 Implicitly print

(If you run this code on ATO instead of TIO then you can also pass σ as a dictionary mapping 0-indexed source indices to destination indices.)

Answer 3

Uiua, 10 bytes

⊏⍜⊙⋯≡⊏¤⊙°⊏

Try it!

Takes input with the permutation as a 0-indexed array of indices, followed by the binary string.

⊏⍜⊙⋯≡⊏¤⊙°⊏
 ⊙°⊏ # create an array of indices
 ⍜⊙⋯ # convert to binary
 ≡⊏¤ # permute the bits
 ⍜⊙⋯ # convert back to numbers
⊏ # index into s

Answer 4

Jelly, 7 bytes

UŒPṬỤỤị

Try it online!

Port of alephalpha's Nekomata answer.

U Reverse p,
 ŒP shortest-first powerset,
 Ṭ untruth (surprised this vectorizes!),
 ỤỤ double grade up (convert to permutation),
 ị index into s.

Jelly, (削除) 9 (削除ここまで) 8 bytes

ịⱮL2ṗɗỤị

Try it online!

Pretty naive implementation. Takes a 1-indexed permutation list \$[\sigma(1), ..., \sigma(n)]\$ on the left, and the string \$s\$ on the right.

 2ṗ Raise [1, 2] to the Cartesian power of
 L the length of the permutation (= n),
ịⱮ ɗ and index the permutation into each result.
 Ụ Grade that up (argsort),
 ị and index into s.

Answer 5

APL(Dyalog Unicode), (削除) 22 (削除ここまで) 10 bytes ^SBCS

Same idea as @Albert.Lang's.

∊⊣⍉2⍨ ̈⍤⊣⍴⊢

Try it on APLgolf!

Try it on APLgolf! 22bytes

BQN, 8 bytes

⥊⊣⍉2 ̇ ̈⊸⥊

Try it on BQNPAD

Answer 6

Python3, 113 bytes

lambda n,s,o:''.join(s[int(''.join(x for _,x in sorted([*zip(o,bin(j)[2:].zfill(n))])),2)]for j in range(len(s)))

Try it online!

• Unrelated String: 188. Also not sure you really need the join or the [0]; output format is pretty lenient.
• Ajax1234: @UnrelatedString Thank you, updated
• Unrelated String: oh, 108
• Unrelated String: *107 (and I'd still maintain that you can go down to 100 without the outer join)
• Unrelated String: *103

Answer 7

Python, (削除) 113 (削除ここまで) 110 bytes

lambda s,p,n:[s[i]for i in g(range(n),*p[::-1])]
g=lambda s,h,*t:sorted(t and g(s,*t)or s,key=lambda i:i>>h&1)

-3 thanks to Karl

Attempt This Online!

Probably golfable and loses to a more direct approach, but this one is just too much fun. (2*&ÞƒJ’$}‘ị for 11 in Jelly--thanks 1-indexing...) Takes an inverse 0-indexed permutation list \$[\sigma^{-1}(0 ),...,\sigma^{-1}(n-1)]\$, where the inverse is equivalently the grade-up, alongside \2ドル^n\$.

Since sorted is stable, this sorts by each bit in permutation order, essentially "bubbling" that bit to most significant (w.r.t. the destination indices) before being "pushed down" by the next.

A little more digestible:

lambda s,p,n:[s[i]for i in reduce(lambda x,h:sorted(x,key=lambda i:i>>h&1),p,range(n))]
from functools import*

• Karl: Took me a few minutes, but I get it! Amusing way to do a recursive reduce by "destructuring the varargs". functools.reduce(lambda s,h: sorted(s,key=lambda i:i>>h&1), p[::-1], range(n))
• Unrelated String: @Karl I've actually seen this done so many times that I assumed it was shorter than importing functools without even trying that... and I was right for the most part, but given that it also obviates the need to reverse p, they actually tie! Also didn't occur to me to take \2ドル^n\$ as input (too Jelly-brained), so that saves 3 bytes on both.

Answer 8

Nekomata, 6 bytes

↔SĦaõ@

Attempt This Online!

Takes the permutation as a 0-indexed list, e.g., [1,2,0] for \$\begin{pmatrix}0&1&2\1円&2&0\end{pmatrix}\$. Takes the binary string as a list of integers, e.g., [1,1,0,1,0,0,1,0] for 11010010.

↔SĦaõ@ Take [1,2,0] [1,1,0,1,0,0,1,0] as an example
↔ Reverse
 -> [0,2,1]
 S Find a subset
 -> [] [0] [2] [0,2] [1] [0,1] [2,1] [0,2,1]
 Ħ Histogram
 -> [] [1] [0,0,1] [1,0,1] [0,1] [1,1] [0,1,1] [1,1,1]
 a All possible values
 -> [[],[1],[0,0,1],[1,0,1],[0,1],[1,1],[0,1,1],[1,1,1]]
 õ Ordering
 -> [0,2,4,6,1,3,5,7]
 @ Index into the second input
 -> [1,0,0,1,1,1,0,0]

Answer 9

K (ngn/k), 14 bytes

Naive implementation. It takes \$\sigma\$ as a 0-indexed premutation vector.

{y@2/(2\!#y)x}

Try it online!