python - 在Python中查找所有唯一的替换组合

Question

给定两个独特标签列表，例如:

a = ['Joe', 'Mary', 'Sue']
b = ['S0', 'S1', 'S2', 'S3', 'S4', 'S5']

如何有效地找到列表 a 中的元素被替换或映射到列表 b 中的所有可能组合？例如如果 S0 = S1 = Joe，S2 = Mary，S3 = S4 = S5 = Sue 那么我会:

{'S0': 'Joe', 'S1': 'Joe', 'S2': 'Mary', 'S3': 'Sue', 'S4': 'Sue', 'S5': 'Sue'}

我从这个简单的嵌套 for 循环方法开始:

def iter_mapping_combos(names1, names2):
    q = [(names2, {})]
    priors = set()
    while q:
        _names2, _mapping = q.pop(0)
        key = (frozenset(_names2), frozenset(_mapping.items()))
        if key in priors:
            continue
        priors.add(key)
        for n1 in names1:
            for n2 in _names2:
                if n2 in _mapping:
                    continue
                _mapping_next = dict(_mapping)
                _mapping_next[n2] = n1
                _names2_next = set(_names2)
                _names2_next.remove(n2)
                if _names2_next:
                    q.append((_names2_next, _mapping_next))
                else:
                    yield _mapping_next

for mapping in iter_mapping_combos(['Joe', 'Mary', 'Sue'], ['S0', 'S1', 'S2', 'S3', 'S4', 'S5']):
    print(mapping)

它可以工作，但正如您可以想象的那样，它效率不高，并且随着列表长度的增加而无法很好地扩展。有更好的方法吗？

Answer 1

您可以使用itertools.product生成所需的笛卡尔积:

from itertools import product

def iter_mapping_combos(names1, names2):
    yield from (dict(zip(names2, p)) for p in product(names1, repeat=len(names2)))

这样:

for mapping in iter_mapping_combos(['Joe', 'Mary'], ['S0', 'S1', 'S2']):
    print(mapping)

输出:

{'S0': 'Joe', 'S1': 'Joe', 'S2': 'Joe'}
{'S0': 'Joe', 'S1': 'Joe', 'S2': 'Mary'}
{'S0': 'Joe', 'S1': 'Mary', 'S2': 'Joe'}
{'S0': 'Joe', 'S1': 'Mary', 'S2': 'Mary'}
{'S0': 'Mary', 'S1': 'Joe', 'S2': 'Joe'}
{'S0': 'Mary', 'S1': 'Joe', 'S2': 'Mary'}
{'S0': 'Mary', 'S1': 'Mary', 'S2': 'Joe'}
{'S0': 'Mary', 'S1': 'Mary', 'S2': 'Mary'}

演示:https://repl.it/repls/BlondStalePostscript