[FIXED] Efficient calculation of all permutations mapping a vector into another in Python?

Issue

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?

Solution

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

Answered By - Onyambu