How can I find the array that permutes one array into another? In particular, I'm looking for a vectorized magic function that takes two unique but permuted arrays as input, and returns the ordering array to permute one to the other. For example:
>>> x1 = np.array([3, 1, 4, 2])
>>> x2 = np.array([2, 1, 3, 4])
>>> sort = magic_function(x1,x2) # such that x1[sort] == x2
>>> print(sort)
array([3, 1, 0, 2])
>>> print(x1[sort])
array([2, 1, 3, 4])
While the function
def find_permutation(x1,x2):
report = np.zeros_like(x1)
for ii in range(len(x1)):
report[ii] = np.argwhere(x1==x2[ii])
return report
works, it isn't vectorized, because of the for loop, so it won't cut it for me.
This should do it:
sort = x1.argsort()[x2.argsort().argsort()]
It works by establishing a common mapping to the sorted values and using the indices to build the (reversed) indirection:
common mapping: 1, 2, 3, 4
x1 [3, 1, 4, 2] ==> [1, 3, 0, 2] x1.argsort()
x2 [2, 1, 3, 4] ==> [1, 0, 2, 3] x2.argsort().argsort()
| | | |
v v v v
indirection (sort): [3 1 0 2] x1.argsort()[x2.argsort().argsort()]
[2, 1, 3, 4] x1[sort] == x2
[EDIT] second example added because 1st example produced same array for x2.argsort() and x2.argsort().argsort() which lead to an incomplete/incorrect answer :
common mapping: 1, 2, 3, 4
x1 [3, 1, 2, 4] ==> [1, 2, 0, 3] x1.argsort()
x2 [4, 1, 2, 3] ==> [3, 0, 1, 2] x2.argsort().argsort()
| | | |
v v v v
indirection : [3, 1, 2, 0] sort
[4, 1, 2, 3] x1[sort] == x2
This is vectorized, works even if x1 contains duplicate values, and has complexities of O(N) space and O(NlogN) time
This could be written as an assignment, so that it only performs 2 sorts instead of 3:
sort = np.zeros_like(x1)
sort[x2.argsort()] = x1.argsort()
all(x1[sort] == x2) # True