# Permute Multidimensional Array without allocation

**URL:** <https://discourse.julialang.org/t/permute-multidimensional-array-without-allocation/29153>\
**Category:** General Usage\
**Created:** [September 25, 2019, 9:47am UTC](https://discourse.julialang.org/t/permute-multidimensional-array-without-allocation/29153 "2019-09-25T09:47:10Z")\
**Posts on this page:** 10\
**Page:** 1

<div class="post-metadata">

**Author:** ![mrVeng](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mrveng/32/8836_2.png) [@mrVeng](https://discourse.julialang.org/u/mrVeng)\
**Post date:** [September 25, 2019, 9:47am UTC](https://discourse.julialang.org/t/permute-multidimensional-array-without-allocation/29153/1 "2019-09-25T09:47:10Z")

</div>

Hi guys,

I am trying to permute/shuffle columns of a multidimensional array, an example is here:

```julia
using BenchmarkTools

const arra = zeros(Int, 4, 3, 2)
arra[:,:, 1] = 1:12
arra[:,:, 2] = 13:24

shuffle_col = [3, 1, 1]

@benchmark arra[:, shuffle_col, :] #solution 1 - works but allocates
@benchmark @view arra[:, shuffle_col, :] #solution 2 - much faster but arra is now a subarray

```

Both solutions work but the first one allocates, and the second one forces me to continue to work with a subarray (which I would like to avoid). I tried to put everything in a function in a loop, but my solution takes longer than the two above for bigger arrays (and needs a copy to work to begin with):

```julia
function permute_col_array!(array::AbstractArray, permutation::Vector{Int}) #, dimension::Int
        temp = copy(array)
        for (i, permute) in enumerate(permutation)
            array[:,i,:] = temp[:,permute,:]
        end
end

@benchmark permute_col_array!(arra, shuffle_col)

```

Does anyone here know if I can permute multidimensional arrays without allocation? I would gain significant improvements in functions if I could do that. There is a base function `permute!` in Julia but it only works on vector elements, not on whole columns.

Best regards,

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [September 25, 2019, 10:17am UTC](https://discourse.julialang.org/t/permute-multidimensional-array-without-allocation/29153/2 "2019-09-25T10:17:11Z")

</div>

Did you test your function? I think it must overwrite some elements before they are used.

---

<div class="post-metadata">

**Author:** ![mrVeng](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mrveng/32/8836_2.png) [@mrVeng](https://discourse.julialang.org/u/mrVeng)\
**Post date:** [September 25, 2019, 10:39am UTC](https://discourse.julialang.org/t/permute-multidimensional-array-without-allocation/29153/3 "2019-09-25T10:39:11Z")

</div>

Thanks it should work now! But my try is now even worse than before as I needed the copy to not overwrite it in a loop.

---

<div class="post-metadata">

**Author:** ![anon92994695](https://avatars.discourse-cdn.com/v4/letter/a/ce7236/32.png) [@anon92994695](https://discourse.julialang.org/u/anon92994695)\
**Post date:** [September 25, 2019, 10:48am UTC](https://discourse.julialang.org/t/permute-multidimensional-array-without-allocation/29153/4 "2019-09-25T10:48:09Z")

</div>

I’ve been stuck trying to solve this problem too! I have a use case for this kind of mechanism that I haven’t been able to crack: [Complex Numbers Wrappers](https://discourse.julialang.org/t/complex-numbers-wrappers/28283)

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [September 25, 2019, 11:15am UTC](https://discourse.julialang.org/t/permute-multidimensional-array-without-allocation/29153/5 "2019-09-25T11:15:12Z")

</div>

AFAIK permuting arrays in place in general is not a trivial problem. If allocation (and not copying) is the costly part _per se_, perhaps you should just [preallocate for output](https://docs.julialang.org/en/v1/manual/performance-tips/#Pre-allocating-outputs-1).

---

<div class="post-metadata">

**Author:** ![mrVeng](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mrveng/32/8836_2.png) [@mrVeng](https://discourse.julialang.org/u/mrVeng)\
**Post date:** [September 25, 2019, 11:21am UTC](https://discourse.julialang.org/t/permute-multidimensional-array-without-allocation/29153/6 "2019-09-25T11:21:37Z")

</div>

Preallocation is unfortunately not possible as I need to shuffle the array in a loop and the object of interest is the array itself ( a filtering problem).

---

<div class="post-metadata">

**Author:** ![LaurentPlagne](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/laurentplagne/32/10103_2.png) [@LaurentPlagne](https://discourse.julialang.org/u/LaurentPlagne)\
**Post date:** [September 25, 2019, 11:32am UTC](https://discourse.julialang.org/t/permute-multidimensional-array-without-allocation/29153/7 "2019-09-25T11:32:07Z")

</div>

Could you elaborate on this ? In place permutations are really difficult to optimize. In 3D you have to compute some permutation cycles… In general out of place (with pre-allocation + ptr swap) permutations are much easier to implement and perform better. If it is simple permutedims you can tile.

---

<div class="post-metadata">

**Author:** ![mrVeng](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mrveng/32/8836_2.png) [@mrVeng](https://discourse.julialang.org/u/mrVeng)\
**Post date:** [September 25, 2019, 11:47am UTC](https://discourse.julialang.org/t/permute-multidimensional-array-without-allocation/29153/8 "2019-09-25T11:47:18Z")

</div>

Here would be a dummy code of what I have to do:

```julia
#Input
observations = Matrix(T,P)

#Algorithm
function myproblem(observations, k, ....)
    #initialize trajectory
    trajectories = Matrix(T,M,N) 
    for i in 1:T
        #get column order
        weights = somefunction(observations[1:i,:], trajectories[:,(i-k):i,:] )
        #Reshuffle trajectories
        trajectories = trajectories[:,weights,:]
    end
    return trajectories
end

```

I can do preallocation for trajectories, but so far I have not found a way for `trajectories[:,weights,:]` to not allocate a new array at each iteration unfortunately. I also cannot simply make a output container as I only know the output after looping through all columns in this case.

Also, looping column by column performs better here than row by row, as I fill the trajectories via columns in this case.

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [September 25, 2019, 12:10pm UTC](https://discourse.julialang.org/t/permute-multidimensional-array-without-allocation/29153/9 "2019-09-25T12:10:46Z")

</div>

(Realize that `array[:,i,:] = temp[:,permute,:]` allocates an a extra copy of the `temp[:,permute,:]` slice unless you use `@views`.)

> [@mrVeng](#):
>
> There is a base function `permute!` in Julia but it only works on vector elements, not on whole columns

There actually is an undocumented `Base.permutecols!!(A, p)` function that permutes the whole columns of a matrix `A` by `p` (also overwriting the permutation array `p`). It’s not very long, and you could base something for 3d arrays off it pretty easily: [https://github.com/JuliaLang/julia/blob/99d1d6723d72d43074b5d2765e63d08439989e8e/base/combinatorics.jl#L66-L95](https://github.com/JuliaLang/julia/blob/99d1d6723d72d43074b5d2765e63d08439989e8e/base/combinatorics.jl#L66-L95)

---

<div class="post-metadata">

**Author:** ![mrVeng](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mrveng/32/8836_2.png) [@mrVeng](https://discourse.julialang.org/u/mrVeng)\
**Post date:** [September 25, 2019, 1:26pm UTC](https://discourse.julialang.org/t/permute-multidimensional-array-without-allocation/29153/10 "2019-09-25T13:26:58Z")

</div>

> [@stevengj](#):
>
> Base.permutecols!!(A, p)

Thank you a lot! I tried to get it to run in Julia 1.2, but failed so far. I will think about how I could extend it to more dimension without copying at least `p`.