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

General Usage
,
1

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!

2

Not at the computer now, but perhaps

findfirst.(B, Ref(A))

Edit: no, wrong if you can have repeated entries

3

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

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
6

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
7

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
8

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
9

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

A

? :slight_smile:

10

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

11 
B[indexin(A,B)]
1 Like