在Python中高效计算将一个向量映射到另一个向量的所有排列？

Question

给定两个向量，我想计算（在Python中）将第一个向量映射到第二个向量的所有排列（作为坐标向量）。这些向量以相同长度的

numpy

数组形式给出，我将它们称为

f_arr

（映射的源向量）和

t_arr

（也是映射的目标向量）。因此，我正在寻找索引向量

perm

的排列

list(range(len(f_arr)))

，其中

f_arr[perm]

等于

t_arr

。向量可以具有重复的元素，这一点很重要。

同样重要的是我不想生成所有排列。例如，这篇文章中的答案对我不起作用： 如何生成列表的所有排列？

我有以下低效代码。我正在寻找一种有效的回溯算法，最好在优化的Python库中实现，它可以使用类似下面的

positions

向量并生成仅将映射

f_arr

到

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}')

打印：

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)

是否有一些Python库可以有效地生成仅有效的排列，将映射

f_arr

到

t_arr

？

Answer 1

您可以使用以下内容：

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