python - 如何获取两个列表之间的所有唯一分配

Question

我有两个列表，每个列表都可以包含重复的值，但任何值只能出现在这两个列表之一(或没有)中。

A = [0,1]
B = [2,3]

我想获取这两个列表之间的所有唯一映射。

assignment(A,B) = [((0,2),(1,3)), ((0,3),(1,2))]

我知道这可以通过使用 itertools.permutations 来完成。 然而，两个列表中的一个/两个都可能有重复项，然后这种方法会给我重复项，因为我不关心分配的顺序。因为对于每个可能的任务，我只想找到总距离。

A = [1,1]
B = [2,3]
mapping(A,B) = [((1,2),(1,3)), ((1,3),(1,2))]

期望的输出是

mapping(A,B) = [((1,2),(1,3))]

如果只有第一个列表重复，我可以使用 sympy.utilities.iterables.multiset_permutations 来实现这一点。虽然这对我来说也不起作用，因为它与 numba 配合不好

但是第二个列表也可能重复，即使这样我也会得到类似的结果

A = [0,1]
B = [3,3]
mapping(A,B) = [((0,3),(1,3)), ((1,3),(0,3))]

期望的输出是

mapping(A,B) = [((0,3),(1,3))]

此外，理想情况下我希望代码能够与 numba 一起使用。 我最好的方法是生成 A 的所有排列，将它们放入一组中以过滤掉重复项，然后执行评估 B 上重复选项的额外工作吗？ (它不会给出错误的结果，只是会减慢代码速度)

目前我最好的猜测是我必须这样做

AB = [list(zip(perm, B)) for perm in set(permutations(A, len(B)))]

与

@njit
def permutations(A, k):
    """Calculates permutation of k elements in A. Needed because numba doesnt like itertools"""
    r = [[i for i in range(0)]]
    for i in range(k):
        r = [[a] + b for a in A for b in r if (a in b) == False]
    return r

并且只需对 B 具有重复项的情况进行额外的工作即可。

编辑: 我现在得到了两个版本，可以给出所需的结果:

set(tuple(sorted(zip(perm, B))) for perm in set(permutations(A, len(B))))

和

set(tuple(sorted(zip(A, p))) for p in permutations(B))

以及生成来自第二个数组的重复项的先前版本

[zip(perm, B) for perm in set(permutations(A, len(B)))]

我还测试了哪个版本对于我的具体用例来说是最快的:

from itertools import product, permutations
import timeit
import numpy as np
A = [0,0,1,1]
B = [2,3,3,3]
mem = np.arange(5)

def vers1(A,B,mem):
    res = float("inf")
    for mapping in set(tuple(sorted(zip(A, p))) for p in permutations(B)):
        temp = 0
        for a, b in mapping:
            temp += abs(mem[a]-mem[b])
        res = min(res,temp)
    return res
    
def vers2(A,B,mem):
    res = float("inf")
    for mapping in set(tuple(sorted(zip(perm, B))) for perm in set(permutations(A, len(B)))):
        temp = 0
        for a, b in mapping:
            temp += abs(mem[a]-mem[b])
        res = min(res,temp)
    return res
    
def vers3(A,B,mem):
    res = float("inf")
    for mapping in [zip(perm, B) for perm in set(permutations(A, len(B)))]:
        temp = 0
        for a, b in mapping:
           temp += abs(mem[a]-mem[b])
        res = min(res,temp)
    return res

print(vers1(A,B,mem))
print(timeit.timeit("vers1(A,B,mem)",'from __main__ import vers1, A, B,mem'))
print(vers2(A,B,mem))
print(timeit.timeit("vers2(A,B,mem)",'from __main__ import vers2, A, B,mem'))
print(vers3(A,B,mem))
print(timeit.timeit("vers3(A,B,mem)",'from __main__ import vers3, A, B,mem'))

得到了这个结果:

9
58.46571195700017
9
23.15174284099703
9
28.064288804998796

Answer 1

使用集合删除重复项

import itertools as it

A=[0,1]
B=[3,3]
AB = list(set(tuple(zip(A, p)) for p in it.permutations(B)))