Finding relative ordering of two lists

Suppose you have two lists A and B which are related by a permutation, and have no repeated elements.

Is there a simple and efficient way of finding the ordering p which satisfies A[[p]]==B?

The best I have is

p = First@FirstPosition[A,#]&/@B;


However, this seems inefficient as it neglects much of the structure of the problem. I imagined there might be a way of using OrderingBy but I couldn't see a way to easily employ it, as it takes a function, rather than a canonical order, as its argument.

• p = OrderingBy[A, Position[B, #] &] Oct 2, 2022 at 15:28

One can use

p = Permute[Ordering[A],Ordering[B]];


Example. Here is an example of length 100000:

A=RandomReal[{-1,1},100000];
B=RandomSample[A];
RepeatedTiming[p = Permute[Ordering[A],Ordering[B]];]

• This seems to be the fastest solution by a reasonable margin. Thank you! Oct 2, 2022 at 20:12
• @ComptonScattering Are your list using numbers, or words, or other type of expressions? Oct 2, 2022 at 20:53
• @AntonAntonov In my particular case each element is a length two list of integers. Oct 2, 2022 at 21:50
• Ok, then the code of this answer is faster than the code in mine. :) (That is not the case if the elements are strings.) Oct 2, 2022 at 22:11

This might be too contrived (first thing that came to mind), but seems to work:

SeedRandom[33];
A = RandomWord[5]
B = RandomSample[A];

(* {"scrooge", "candelabra", "together", "jotting", "remorseful"} *)

{aA, aB} = AssociationThread[#, Range[Length[#]]] & /@ {A, B}

(* {<|"scrooge" -> 1, "candelabra" -> 2, "together" -> 3,
"jotting" -> 4, "remorseful" -> 5|>, <|"scrooge" -> 1,
"candelabra" -> 2, "jotting" -> 3, "remorseful" -> 4,
"together" -> 5|>} *)

A[[Values[KeyTake[aA, Keys[aB]]]]] == B

(* True *)
$$$$


FindPermutation almost does this but it gives the output in terms of Cycles. The name is easy to remember if needed for later use but it is slower than the fastest method here (two times slower than the method in @293787's answer with the test list given in that answer). If you would like the ordering as a list then :

Permute[Range[Length[A]], FindPermutation[A, B]]


We may create the permutation that changes A to B by:

perm = (Position[B, #][[1, 1]]) & /@ A


With "perm", we can now permute A into B:

Permute[A, perm]

• But this is not significantly faster than OPs code. Try to apply this when A=RandomReal[{-1,1},100000]; B=RandomSample[A];` for example. I think OP specifically asks for more efficient code. Oct 2, 2022 at 17:17