Замените заполнитель в строке ключами словаря

Question

Предположим, у меня есть:

• строка-заполнитель "aabbaaa"
• и словарь: {'A': 'a', 'B': 'a', 'C': 'b', 'D': 'a', 'E': 'b', 'F': 'a', 'G': 'b'}.

Как мне создать в python все возможные перестановки из словарных ключей для строки заполнителя?

Ожидаемый результат, например, будет:

AACCAAA, AACCAAB, AACCABA, ... AACEAA, AACEAA, AAEEAA ..., FFGGFFF et c.

Answer 1

Решение может быть:

    >>> import itertools
    >>> from collections import defaultdict
    >>> dict_ = defaultdict(list)
    >>> input = "ab"
    >>> _dict = {'A': 'a', 'B': 'a', 'C': 'b', 'D': 'a', 'E': 'b', 'F': 'a', 'G': 'b'}
    >>> for k,v in _dict.items():
    ...     dict_[v].append(k)
    ... 
    >>> _iterables = [dict_[character] for character in input]
    >>> output = [''.join(tup) for tup in itertools.product(*_iterables)]
    set(['BE', 'AC', 'BG', 'AE', 'AG', 'BC', 'DG', 'DE', 'DC', 'FC', 'FE', 'FG'])

Дайте мне знать, если это поможет !!

Answer 2

Вы можете построить всю перестановку с помощью обратного отслеживания.

Сначала дикт будет более полезным, если его поменять местами, так что сделайте это:

from collections import defaultdict
orig_str = "aabbaaa"
d =  {'A': 'a', 'B': 'a', 'C': 'b', 'D': 'a', 'E': 'b', 'F': 'a', 'G': 'b'}
reverse_d = defaultdict(list)
for k, el in d.items():
    reverse_d[el].append(k)

И здесь мы имеем reverse_d = {'a': ['A', 'B', 'D', 'F'], 'b': ['C', 'E', 'G']}

Далее мы можем написать нашу функцию обратного отслеживания, которая для любого символа строки упорядочит возможности:

def permut(orig_str, index, chars_till_now):
    if index == len(orig_str):
        print("".join(chars_till_now))
        return
    chars = chars_till_now[:]
    chars.append("")
    for possibility in reverse_d[orig_str[index]]:
        chars[-1] = possibility
        permut(orig_str, index+1, chars)

Вы можете изменить функцию, чтобы сохранить перестановку, а не печатать или передавать определите c словарь, а не используйте один глобальный; это зависит от того, что вам нужно.

Для вызова функции просто:

permut(orig_str, 0, [])