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

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!

Not at the computer now, but perhaps

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

Edit: no, wrong if you can have repeated entries

Just an untested idea:

``````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).

1 Like
``````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`.

2 Likes

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> 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

``````
1 Like

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.

2 Likes

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

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

with no ambition to compete with any of the proposed solutions

``````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

``````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> 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
``````

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

``````A
``````

?

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.–