Given two vectors, I would like to calculate (in Python) all permutations (as vectors of coordinates) which map the first vector into the second. The vectors are given as numpy arrays of the same length, I call them f_arr (the source vector mapping from) and t_arr (the target vector mapping too). So I am looking for permutations perm of the index vector list(range(len(f_arr))) for which f_arr[perm] becomes equal to t_arr. It is important that the vectors can have repeated elements.
It is also important that I do not want to generate all the permutations. For example, the answers in this post do not work for me: How do I generate all permutations of a list?
I have the following inefficient code. What I am looking for is an efficient backtracking algorithm, preferably implemented in an optimized Python library, which can use something like the positions vector below and generate only the valid permutations which map f_arr to t_arr.
f_arr = np.array([1,2,3,4,3,4], dtype=np.uint8) # vector mapping from
t_arr = np.array([3,1,4,3,4,2], dtype=np.uint8) # vector mapping to
positions = [np.where(f_arr == a)[0] for a in t_arr]
for perm in itertools.product(*positions):
if len(perm) == len(set(perm)):
print(f'{perm} -> {f_arr[list(perm)]}')
else: # this branch is only for demonstration
print(f'Not a permutation: {perm}')
which prints:
Not a permutation: (2, 0, 3, 2, 3, 1)
Not a permutation: (2, 0, 3, 2, 5, 1)
Not a permutation: (2, 0, 3, 4, 3, 1)
(2, 0, 3, 4, 5, 1) -> [3 1 4 3 4 2]
Not a permutation: (2, 0, 5, 2, 3, 1)
Not a permutation: (2, 0, 5, 2, 5, 1)
(2, 0, 5, 4, 3, 1) -> [3 1 4 3 4 2]
Not a permutation: (2, 0, 5, 4, 5, 1)
Not a permutation: (4, 0, 3, 2, 3, 1)
(4, 0, 3, 2, 5, 1) -> [3 1 4 3 4 2]
Not a permutation: (4, 0, 3, 4, 3, 1)
Not a permutation: (4, 0, 3, 4, 5, 1)
(4, 0, 5, 2, 3, 1) -> [3 1 4 3 4 2]
Not a permutation: (4, 0, 5, 2, 5, 1)
Not a permutation: (4, 0, 5, 4, 3, 1)
Not a permutation: (4, 0, 5, 4, 5, 1)
Is there some Python library which can efficiently generate only the valid permutations which map f_arr to t_arr?
You could use the following:
from itertools import permutations, product
import numpy as np
def map_vec(vec1, vec2):
i1 = vec1.argsort()
i2 = vec2.argsort()
i3 = i1[i2[i1].argsort()]
_, b = np.unique(vec2[i2], return_index = True)
c = [permutations(i) for i in np.split(i1, b)]
return np.array([np.r_[i] for i in product(*c)], int)[:,i3]
map_vec(f_arr, t_arr)
array([[2, 0, 3, 4, 5, 1],
[2, 0, 5, 4, 3, 1],
[4, 0, 3, 2, 5, 1],
[4, 0, 5, 2, 3, 1]])
Here is a pythonic explanation on what the code is doing:
from itertools import permutations, product
import numpy as np
f_arr = np.array([1,2,3,4,3,4], dtype=np.uint8) # vector mapping from
t_arr = np.array([3,1,4,3,4,2], dtype=np.uint8) # vector mapping to
i1 = f_arr.argsort() # the ordered positions of first array
i2 = t_arr.argsort()[i1].argsort() # the index of the second array in first array
print(i2)
# [2 0 3 4 5 1]
The first value (3) in the second array is in position 2 of the first array, the second value (1) is in position 0 of the first array etc.
out = {} # dict holding indices for unique elements in f_arr
for i, j in enumerate(f_arr):
out[j] = out.get(j, []) + [i]
for i, j in out.items():
if len(j) > 1:
out[i] = list(permutations(j)) # coerced to list to visualize. No need to do so.
print(out)
# {1: [0], 2: [1], 3: [(2, 4), (4, 2)], 4: [(3, 5), (5, 3)]}
a = np.c_[[np.r_[i] for i in product(*out.values())]]
print(a)
array([[0, 1, 2, 4, 3, 5], # the indices for sorted f_arr: 1,2,3,3,4,4
[0, 1, 2, 4, 5, 3],
[0, 1, 4, 2, 3, 5],
[0, 1, 4, 2, 5, 3]])
a[:, i1[i2]] # ordering back. indices for 3,1,4,3,4,2
array([[2, 0, 3, 4, 5, 1],
[2, 0, 5, 4, 3, 1],
[4, 0, 3, 2, 5, 1],
[4, 0, 5, 2, 3, 1]])