# In-place inverse permutation

**URL:** <https://discourse.julialang.org/t/in-place-inverse-permutation/94368>\
**Category:** Performance\
**Tags:** sort, sortperm\
**Created:** [February 9, 2023, 5:48pm UTC](https://discourse.julialang.org/t/in-place-inverse-permutation/94368 "2023-02-09T17:48:32Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![jacob-roth](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jacob-roth/32/1862_2.png) [@jacob-roth](https://discourse.julialang.org/u/jacob-roth)\
**Post date:** [February 9, 2023, 5:48pm UTC](https://discourse.julialang.org/t/in-place-inverse-permutation/94368/1 "2023-02-09T17:48:32Z")

</div>

Is there a reason that there is not an in-place equivalent of `sortperm!`, i.e., “`invperm!`”?

One current (v1.8.3) approach would be to call `invpermute!(v, sig)` for permutation `sig`, but the docs say that for `v` with many elements, `v[sig]` is faster than `permute!(v,sig)` so I would think that the same is true for `v[siginv]` versus `invpermute!(v, sig)`.

---

<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:** [February 9, 2023, 6:16pm UTC](https://discourse.julialang.org/t/in-place-inverse-permutation/94368/2 "2023-02-09T18:16:46Z")

</div>

> [@jacob-roth](#):
>
> “`invperm!`”?

Is there a reasonably efficient in-place algorithm for this? I doubt it…

> [@jacob-roth](#):
>
> for `v` with many elements, `v[sig]` is faster than `permute!(v,sig)` so I would think that the same is true for `v[siginv]` versus `invpermute!(v, sig)`

The fastest is to do `u[p] = v` with a pre-allocated output array `u`. Then you don’t need the inverse permutation `pinv = invperm(p)` at all. For example:

```julia
julia> using BenchmarkTools, Random

julia> p = randperm(100); v = rand(100); u = similar(v); pinv = invperm(p);

julia> @btime $v[$pinv];
  90.787 ns (1 allocation: 896 bytes)

julia> @btime permute!($v, $pinv);
  283.500 ns (1 allocation: 896 bytes)

julia> @btime $u .= @view $v[$pinv];
  70.441 ns (0 allocations: 0 bytes)

julia> @btime $u[:] = @view $v[$pinv];
  103.679 ns (0 allocations: 0 bytes)

julia> @btime invpermute!($v, $p);
  311.929 ns (1 allocation: 896 bytes)

julia> @btime $u[$p] = $v;
  48.583 ns (0 allocations: 0 bytes)

```

So, `u[p] = v` is _by far_ the fastest way to perform an inverse permutation, not even counting the time it would take to compute `pinv = invperm(p)` (about 94ns on my machine).

Note that even the “in-place” functions `permute!` and `invpermute!` need to do some allocation internally (the former to keep track of which elements have already been permuted, the latter to simply run [`v[p] = v`](https://github.com/JuliaLang/julia/blob/3653d3d05ffb8a652b12ff22e550ec8fe07edd1d/base/combinatorics.jl#L234) with a copy). [Efficient in-place permutation is hard!](https://stackoverflow.com/questions/16501424/algorithm-to-apply-permutation-in-constant-memory-space) It’s hard [even when the permutation has a simple mathematical formula](https://en.wikipedia.org/wiki/In-place_matrix_transposition)!

I submitted a documentation patch to clarify this: [permute! and invpermute! - explain fully in-place alternatives by stevengj · Pull Request #48609 · JuliaLang/julia · GitHub](https://github.com/JuliaLang/julia/pull/48609)