# Find permutation of an array such that it is equal to another array

**URL:** <https://discourse.julialang.org/t/find-permutation-of-an-array-such-that-it-is-equal-to-another-array/85365>\
**Category:** General Usage\
**Tags:** question, sortperm\
**Created:** [August 5, 2022, 6:38pm UTC](https://discourse.julialang.org/t/find-permutation-of-an-array-such-that-it-is-equal-to-another-array/85365 "2022-08-05T18:38:43Z")\
**Posts on this page:** 11\
**Page:** 1

<div class="post-metadata">

**Author:** ![heindelj](https://avatars.discourse-cdn.com/v4/letter/h/a6a055/32.png) [@heindelj](https://discourse.julialang.org/u/heindelj)\
**Post date:** [August 5, 2022, 6:38pm UTC](https://discourse.julialang.org/t/find-permutation-of-an-array-such-that-it-is-equal-to-another-array/85365/1 "2022-08-05T18:38:43Z")

</div>

I have a rather simple question that I’m surprised I haven’t been able to figure out easily.

Suppose I have two arrays, `A=["A","C","B","C"]`, and `B=["C","B","A","C"]`.

Treat `A` as the correct sorted order of the array. How do I find the permutation of array `B` such that the two arrays are equal. Assume the arrays are guaranteed to be able to be sorted in this manner.

I feel like this should be rather trivial with the built in sorting function, but I couldn’t figure it out. Any help would be greatly appreciated!

---

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [August 5, 2022, 6:44pm UTC](https://discourse.julialang.org/t/find-permutation-of-an-array-such-that-it-is-equal-to-another-array/85365/2 "2022-08-05T18:44:46Z")

</div>

Not at the computer now, but perhaps

```julia
findfirst.(B, Ref(A))

```

Edit: no, wrong if you can have repeated entries

---

<div class="post-metadata">

**Author:** ![JM\_Beckers](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jm_beckers/32/22482_2.png) [@JM\_Beckers](https://discourse.julialang.org/u/JM_Beckers)\
**Post date:** [August 5, 2022, 7:20pm UTC](https://discourse.julialang.org/t/find-permutation-of-an-array-such-that-it-is-equal-to-another-array/85365/3 "2022-08-05T19:20:23Z")

</div>

Just an untested idea:

```julia
Spa=sortperm(A)
Spb=sortperm(B)

```

allows to know how to sort both arrays to the same sortet array. Then if you want to sort towards the order of A you can use invperm(Spa).

So apply Spb then invperm(Spa).

---

<div class="post-metadata">

**Author:** ![pitsianis](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pitsianis/32/26588_2.png) [@pitsianis](https://discourse.julialang.org/u/pitsianis)\
**Post date:** [August 5, 2022, 7:21pm UTC](https://discourse.julialang.org/t/find-permutation-of-an-array-such-that-it-is-equal-to-another-array/85365/4 "2022-08-05T19:21:43Z")

</div>

```julia
B[sortperm(B)[invperm(sortperm(A))]]

```

i.e. sort array `B` and then follow backwords the sorting permutation of array `A`, to make `B` into `A`.

---

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [August 5, 2022, 10:01pm UTC](https://discourse.julialang.org/t/find-permutation-of-an-array-such-that-it-is-equal-to-another-array/85365/5 "2022-08-05T22:01:23Z")

</div>

Actually, the correct implementation of what I posted above works, if the values are immutable (thus identical values are really identical). And is rather faster:

```julia
julia> a = ['a', 'c', 'b', 'c']; b = ['c', 'b', 'c', 'a'];

julia> f(a,b) = b[sortperm(b)[invperm(sortperm(a))]]
f (generic function with 1 method)

julia> g(a,b) = b[findfirst.(isequal.(a), Ref(b))]
g (generic function with 1 method)

julia> @btime f($a,$b);
  371.766 ns (7 allocations: 496 bytes)

julia> @btime g($a,$b);
  87.014 ns (3 allocations: 192 bytes)

julia> f(a,b) == g(a,b)
true

```

---

<div class="post-metadata">

**Author:** ![rafael.guerra](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rafael.guerra/32/216610_2.png) [@rafael.guerra](https://discourse.julialang.org/u/rafael.guerra)\
**Post date:** [August 5, 2022, 11:14pm UTC](https://discourse.julialang.org/t/find-permutation-of-an-array-such-that-it-is-equal-to-another-array/85365/6 "2022-08-05T23:14:23Z")

</div>

The end result with `findfirst` is the same in this case, but the resulting list of indices is not a permutation, as distinct indices would be required.

---

<div class="post-metadata">

**Author:** ![rafael.guerra](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rafael.guerra/32/216610_2.png) [@rafael.guerra](https://discourse.julialang.org/u/rafael.guerra)\
**Post date:** [August 5, 2022, 11:26pm UTC](https://discourse.julialang.org/t/find-permutation-of-an-array-such-that-it-is-equal-to-another-array/85365/7 "2022-08-05T23:26:06Z")

</div>

Also, the conclusion about performance wouldn’t be the same if the inputs are vectors of integers as follows:

```julia
a = rand(1:100, 1000)
b = shuffle(a)

```

---

<div class="post-metadata">

**Author:** ![rocco\_sprmnt21](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rocco_sprmnt21/32/20127_2.png) [@rocco\_sprmnt21](https://discourse.julialang.org/u/rocco_sprmnt21)\
**Post date:** [August 6, 2022, 1:52pm UTC](https://discourse.julialang.org/t/find-permutation-of-an-array-such-that-it-is-equal-to-another-array/85365/8 "2022-08-06T13:52:13Z")

</div>

with no ambition to compete with any of the proposed solutions

```julia
function dualperm(u,v)
    un=unique(v)
    du=mapreduce(b->findall(==(b),u),vcat, un)
    dv=mapreduce(b->findall(==(b),v),vcat, un)
    u2v=last.(sort(tuple.(du,dv), by=first))
    v2u=first.(sort(tuple.(du,dv), by=last))
    (u2v, v2u)
end

julia> v[dualperm(u,v)[1]]==u
true

julia> 

julia> u[dualperm(u,v)[2]]==v
true

```

this is much better

```julia
function dp(u,v)
    l=length(v)
    tv=last.(sort(collect(zip(v,1:l))))
    tu=last.(sort(collect(zip(u,1:l))))
    last.(sort(tuple.(tu,tv)))
end

```

```julia
julia> v=[1,2,1,3,3,2,4]
7-element Vector{Int64}:
 1
 2
 1
 3
 3
 2
 4

julia> u=[2,1,3,3,1,4,2]
7-element Vector{Int64}:
 2
 1
 3
 3
 1
 4
 2
julia> function dperm(u,v)
       l=length(v)
       last.(sort(tuple.(last.(sort(collect(zip(u,1:l)))),last.(sort(collect(zip(v,1:l)))))))
       end
dperm (generic function with 1 method)

julia> @btime v[dperm(u,v)]
  288.627 ns (11 allocations: 1.44 KiB)
7-element Vector{Int64}:
 2
 1
 3
 3
 1
 4
 2

julia> @btime v[sortperm(v)[Base.invperm(sortperm(u))]]
  430.808 ns (7 allocations: 592 bytes)
7-element Vector{Int64}:
 2
 1
 3
 3
 1
 4
 2

```

---

<div class="post-metadata">

**Author:** ![s-broda](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/s-broda/32/3946_2.png) [@s-broda](https://discourse.julialang.org/u/s-broda)\
**Post date:** [August 6, 2022, 8:56pm UTC](https://discourse.julialang.org/t/find-permutation-of-an-array-such-that-it-is-equal-to-another-array/85365/9 "2022-08-06T20:56:54Z")

</div>

Slightly in jest: since we’re assuming that such a permutation exists, isn’t this equivalent to just

```julia
A

```

? 🙂

---

<div class="post-metadata">

**Author:** ![pitsianis](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pitsianis/32/26588_2.png) [@pitsianis](https://discourse.julialang.org/u/pitsianis)\
**Post date:** [August 8, 2022, 2:17pm UTC](https://discourse.julialang.org/t/find-permutation-of-an-array-such-that-it-is-equal-to-another-array/85365/10 "2022-08-08T14:17:26Z")

</div>

It is the identical reason we need `sortperm`. Oftentimes we need the permutation to permute data according to a given order of a “key” field. Permuting data is faster than sorting, in theory --and in practice, if implemented efficiently.–

---

<div class="post-metadata">

**Author:** ![rocco\_sprmnt21](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rocco_sprmnt21/32/20127_2.png) [@rocco\_sprmnt21](https://discourse.julialang.org/u/rocco_sprmnt21)\
**Post date:** [May 31, 2023, 8:08pm UTC](https://discourse.julialang.org/t/find-permutation-of-an-array-such-that-it-is-equal-to-another-array/85365/11 "2023-05-31T20:08:36Z")

</div>

```julia
B[indexin(A,B)]

```