Поиск всех уникальных комбинаций замен в Python

Учитывая два списка уникальных меток, таких как:

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

Как мне эффективно найти все возможные комбинации, в которых элементы из списка a заменяются или отображаются в список b? например Если S0 = S1 = Джо, S2 = Мэри, S3 = S4 = S5 = Сью, то я бы имел:

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

Это работает, но, как вы можете себе представить, это не так эффективно и плохо масштабируется по мере увеличения длины списков. Есть лучший способ сделать это?


python combinatorics
person Cerin    schedule 25.09.2019    source источник

Ответы (4)


arrow_upward
2
arrow_downward

Вы можете использовать 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

person blhsing    schedule 25.09.2019
comment
После повторного рассмотрения этого вопроса я считаю, что это наиболее эффективный метод для создания желаемых комбинаций. - person Alexander; 28.09.2019

arrow_upward
1
arrow_downward

Вы можете сгенерировать нужные комбинации, а затем использовать zip:

a = ['Joe', 'Mary', 'Sue']
b = ['S0', 'S1', 'S2', 'S3', 'S4', 'S5']
def combos(d, c = []):
  if len(b) == sum(map(len, c)):
     yield c
  for i in range(1, len(d)+1):
     yield from combos(d[i:], c+[d[:i]])

r = [[[j for _ in k] for j, k in zip(a, i)] for i in combos(b) if len(i) == 3]
result = [dict(zip(b, [i for k in j for i in k])) for j in r]

Выход:

[{'S0': 'Joe', 'S1': 'Mary', 'S2': 'Sue', 'S3': 'Sue', 'S4': 'Sue', 'S5': 'Sue'}, {'S0': 'Joe', 'S1': 'Mary', 'S2': 'Mary', 'S3': 'Sue', 'S4': 'Sue', 'S5': 'Sue'}, {'S0': 'Joe', 'S1': 'Mary', 'S2': 'Mary', 'S3': 'Mary', 'S4': 'Sue', 'S5': 'Sue'}, {'S0': 'Joe', 'S1': 'Mary', 'S2': 'Mary', 'S3': 'Mary', 'S4': 'Mary', 'S5': 'Sue'}, {'S0': 'Joe', 'S1': 'Joe', 'S2': 'Mary', 'S3': 'Sue', 'S4': 'Sue', 'S5': 'Sue'}, {'S0': 'Joe', 'S1': 'Joe', 'S2': 'Mary', 'S3': 'Mary', 'S4': 'Sue', 'S5': 'Sue'}, {'S0': 'Joe', 'S1': 'Joe', 'S2': 'Mary', 'S3': 'Mary', 'S4': 'Mary', 'S5': 'Sue'}, {'S0': 'Joe', 'S1': 'Joe', 'S2': 'Joe', 'S3': 'Mary', 'S4': 'Sue', 'S5': 'Sue'}, {'S0': 'Joe', 'S1': 'Joe', 'S2': 'Joe', 'S3': 'Mary', 'S4': 'Mary', 'S5': 'Sue'}, {'S0': 'Joe', 'S1': 'Joe', 'S2': 'Joe', 'S3': 'Joe', 'S4': 'Mary', 'S5': 'Sue'}]
person Ajax1234    schedule 25.09.2019

arrow_upward
1
arrow_downward

Хотя вы не указали свои требования к проблеме, из одного примера я понял, что вам нужно сопоставить каждый элемент b точно с одним элементом a (хотя данный элемент a может иметь более одного b элемент, сопоставленный с ним). Это имеет экспоненциальный взрыв, всего len(b) ** len(a) различных отображений.

Вы можете немного сократить свой код: научитесь использовать модуль itertools; это фактически применение метода product, пересекающее шесть копий a. Проще говоря:

product(*[a]*len(b))

Это тебя заводит?

person Prune    schedule 25.09.2019

arrow_upward
1
arrow_downward

Обратите внимание, что ваш метод пересчитывает в 6 раз (т.е. количество элементов в b). Например, в моем меньшем примере ваш код создает следующее, которое представляет собой просто перестановку одних и тех же элементов:

[{'S0': 'Joe', 'S2': 'Joe', 'S1': 'Joe'},
 {'S0': 'Joe', 'S1': 'Joe', 'S2': 'Joe'},
 {'S1': 'Joe', 'S2': 'Joe', 'S0': 'Joe'},
 ...]

Используя меньший пример, чтобы продемонстрировать мою реализацию:

from itertools import combinations_with_replacement, permutations

a = ['Joe', 'Mary'] 
b = ['S0', 'S1', 'S2'] 

result = []
combos = combinations_with_replacement(a, len(b))
for combo in combos:
    seen = set()
    for p in permutations(range(len(b)), len(b)):
        order = tuple(combo[idx] for idx in p)
        if order not in seen:
            seen.add(order)
            result.append(order)

>>> result
[('Joe', 'Joe', 'Joe'),
 ('Joe', 'Joe', 'Mary'),
 ('Joe', 'Mary', 'Joe'),
 ('Mary', 'Joe', 'Joe'),
 ('Joe', 'Mary', 'Mary'),
 ('Mary', 'Joe', 'Mary'),
 ('Mary', 'Mary', 'Joe'),
 ('Mary', 'Mary', 'Mary')]

Затем результат необходимо закодировать в ключи в b:

final_result = [{b[n]: val for n, val in enumerate(row)} 
                for row in result]
>>> final_result
[{'S0': 'Joe', 'S1': 'Joe', 'S2': 'Joe'},
 {'S0': 'Joe', 'S1': 'Joe', 'S2': 'Mary'},
 {'S0': 'Joe', 'S1': 'Mary', 'S2': 'Joe'},
 {'S0': 'Mary', 'S1': 'Joe', 'S2': 'Joe'},
 {'S0': 'Joe', 'S1': 'Mary', 'S2': 'Mary'},
 {'S0': 'Mary', 'S1': 'Joe', 'S2': 'Mary'},
 {'S0': 'Mary', 'S1': 'Mary', 'S2': 'Joe'},
 {'S0': 'Mary', 'S1': 'Mary', 'S2': 'Mary'}]
person Alexander    schedule 25.09.2019