A Dance of Many Dimensions

Question

Challenge

Given a n-dimensional array of integers and a permutation of the first n natural numbers, permute the array dimensions accordingly.

Details

This challenge is inspired by MATLABs permute. ^{_{demonstration}} The permutation is given as a list of integers, e.g. [1,3,2] means 1 gets mapped to 1, 2 gets mapped to 3 and 3 gets mapped to 2 (here the ith entry is the value i gets mapped to). But you can use other formats that are convenient, for instance as cycles or as a function. If it is more convenient you can also use 0-based indexing.

The array can be assumed to be a full "rectangular" m1 x m2 x ... x mn-array (i.e. you can assume it is not ragged/jagged).

You can assume that n is not too large, as many languages have a limit of the number of dimensions in a nested array.

If your language does not support multidimensional arrays, you can also take a string that represents the array as input.

Examples

• Any n-dimensional array with the identity permutation [1,2,3,...,n] will be unchanged.
• The array [[10,20,30],[40,50,60]] with the permutation [2,1] gets mapped to [[10,40],[20,50],[30,60]].
• The array [[[1,2],[3,4]],[[5,6],[7,8]]] with the permutation [2,3,1] gets mapped to [[[1,3],[5,7]],[[2,4],[6,8]]].

Answer 1

Languages with built-in solutions

based on this proposal by xnor

APL (Dyalog Unicode), 1 byte

⍉

Try it online!

J, 2 bytes

|:

Try it online!

R, 5 bytes

aperm

Try it online!

Octave/MATLAB, 8 bytes

@permute

Try it online!

Wolfram Language (Mathematica), 9 bytes

Transpose

Try it online!

Julia, 11 bytes

permutedims

Try it online!

Answer 2

Haskell, 168 bytes

p is a (type class polymorphic) function taking a permutation as a list of Ints, and a nested list representing a multidimensional array of Ints.

Call as p [2,1] [[10,20,30],[40,50,60]], however if type defaulting doesn't succeed, you may have to add a type annotation like :: [[Int]] (nested appropriately) giving the type of the result.

import Data.List
class P a where p::[Int]->[a]->[a]
instance P Int where p _=id
instance P a=>P[a]where p(x:r)m|n<-p r<$>m,y:z<-sort r=last$n:[p(x:z)<$>transpose n|x>y]

Try it online!

Golfing challenges with nested arrays of arbitrary depth are a bit awkward in Haskell, because the static typing tends to get in the way. While Haskell lists (with the exact same syntax as in the challenge description) can be nested just fine, lists of different nesting depth are of incompatible types. Also, standard Haskell parsing functions require knowing the type of the value you are trying to parse.

As a result, it seems inevitable that the program needs to include type-related declarations, which are relatively verbose. For the golfed part, I settled on defining a type class P, such that p can be polymorphic over the type of the array.

Meanwhile, the TIO's testing harness shows a way to get around the parsing problem.

How it works

• To sum up the essence of this algorithm: It performs a bubble sort on the permutation list, transposing neighboring dimensions when the corresponding permutation indices are swapped.

• As given by the class P a declaration, in any instance, p takes two arguments, a permutation (always of type [Int]) and an array.

• The permutation can be given in the form in the challenge description, although the way the algorithm works, the choice of indices is arbitrary, except for their relative order. (So both 0- and 1- based work.)
• The base instance P Int handles arrays of dimension 1, which p simply returns unchanged, since the one dimension can only be mapped to itself.
• The other instance P a => P [a] is defined recursively, calling p with dimension n subarrays in order to define it for dimension n+1 arrays.
  • p(x:r)m first calls p r recursively on every element of m, giving a result array n in which all dimensions except the first have been permuted correctly relatively to each other.
  • The remaining permutation that needs to be performed on n is given by x:y:z = x:sort r.
  • If x<y then the first dimension of n is already correctly placed, and n is simply returned.
  • If x>y, then the first and second dimension of n need to be swapped, which is done with the transpose function. Finally p(x:z) is applied recursively to every element of the result, ensuring the original first dimension is transposed to the right position.

Answer 3

Python 2, 312 bytes

This uses 0-indexing for the permutation

from numpy import*
from itertools import*
z=range
def f(i,r):
	l=array(i).shape;R={b:a for a,b in enumerate(r)};r=len(r);m=eval('['*r+'0'+q('for k in z(l[R[%s]])]',r-1,-1,-1))
	for d in product(*[z(p) for p in l]):exec'm'+q('[d[R[%s]]]',r)+'=i'+q('[d[%s]]',r)
	return m
q=lambda s,*j:''.join(s%(j)for j in z(*j))

Try it online!

-2 bytes thanks to @Jonathan Frech.

Answer 4

Python 2, 41 25 bytes

import numpy
numpy.einsum

Try it online!

The permutation vector p is given as a string of letters. So [2,3,1] can be be given as 'bca'.

Thanks to @EriktheOutgolfer saved 16 bytes!

Answer 5

JavaScript (ES6), 136 132 bytes

(a,p,v=[],r=[],g=(a,[d,...p],_,h=(r,[i,...v])=>1/v[0]?h(r[i]=r[i]||[],v):r[i]=a)=>1/d?a.map((e,i)=>g(e,p,v[d]=i)):h(r,v))=>g(a,p)&&r

0-indexed. Explanation: g recursively iterates over the array a building up an array v of indices reordered using the permutation p. Once p is exhausted, h then recursively inserts the element into the result array r using the permuted indices.