Комбинации замены строки

Question

Итак, у меня есть строка "1xxx1", и я хочу заменить определенное число (может быть, все, может быть, ни одного) x на символ, скажем, "5". Я хочу, чтобы все возможные комбинации (... возможно, перестановки) строки, где х либо заменен или оставлен как х. Я хотел бы, чтобы эти результаты сохранялись в списке.

Таким образом, желаемый результат будет

>>> myList = GenerateCombinations('1xxx1', '5')
>>> print myList
['1xxx1','15xx1','155x1','15551','1x5x1','1x551','1xx51']

Очевидно, я бы хотел, чтобы он мог обрабатывать строки любой длины с любым количеством х, а также заменять любое число. Я пытался использовать циклы и рекурсию, чтобы понять это безрезультатно. Любая помощь будет оценена.

Answer 1

Как насчет:

from itertools import product

def filler(word, from_char, to_char):
    options = [(c,) if c != from_char else (from_char, to_char) for c in word]
    return (''.join(o) for o in product(*options))

который дает

>>> filler("1xxx1", "x", "5")
<generator object <genexpr> at 0x8fa798c>
>>> list(filler("1xxx1", "x", "5"))
['1xxx1', '1xx51', '1x5x1', '1x551', '15xx1', '15x51', '155x1', '15551']

(Обратите внимание, что вы, кажется, пропали без вести 15x51.) Сначала мы составляем список всех возможных целей для каждой буквы в исходном слове:

>>> word = '1xxx1'
>>> from_char = 'x'
>>> to_char = '5'
>>> [(c,) if c != from_char else (from_char, to_char) for c in word]
[('1',), ('x', '5'), ('x', '5'), ('x', '5'), ('1',)]

И тогда мы используем itertools.product чтобы получить декартово произведение этих возможностей и объединить результаты.

Для получения бонусных баллов измените, чтобы принять словарь замен.:^)

Answer 2

Сгенерируйте значения-кандидаты для каждой возможной позиции — даже если для большинства позиций есть только один кандидат — затем создайте декартово произведение этих значений.

В примере OP кандидаты['x', '5']на любую должность, где'x'появляется на входе; для каждой другой должности кандидаты представляют собой список с единственной возможностью (исходное письмо). Таким образом:

      def candidates(letter):
    return ['x', '5'] if letter == 'x' else [letter]

Затем мы можем создать шаблоны, создав список кандидатов на должности, используяitertools.product, и их объединение:

      from itertools import product

def combine(candidate_list):
    return ''.join(candidate_list)

def patterns(data):
    all_candidates = [candidates(element) for element in data]
    for result in product(*all_candidates):
        yield combine(result)

Давайте проверим это:

      >>> list(patterns('1xxx1'))
['1xxx1', '1xx51', '1x5x1', '1x551', '15xx1', '15x51', '155x1', '15551']

Обратите внимание, что алгоритм в генераторе полностью общий; все, что меняется, — это детали того, как генерировать кандидатов и как обрабатывать результаты. Например, предположим, что мы хотим заменить «заполнители» в строке — тогда нам нужно разделить строку на заполнители и не заполнители и иметь функцию, которая генерирует все возможные замены для заполнителей, и литеральную строку для не заполнителей. .

Например, с этой настройкой:

      keywords = {'wouldyou': ["can you", "would you", "please"], 'please': ["please", "ASAP"]}

template = '((wouldyou)) give me something ((please))'

Сначала мы разделим шаблон, например, с помощью регулярного выражения:

      import re

def tokenize(t):
    return re.split(r'(\(\(.*?\)\))', t)

Этот токенизатор будет выдавать пустые строки до и после заполнителей, но это не вызывает проблемы:

      >>> tokenize(template)
['', '((wouldyou))', ' give me something ', '((please))', '']

Для создания замен мы можем использовать что-то вроде:

      def candidates(part):
    if part.startswith('((') and part.endswith('))'):
        return keywords.get(part[2:-2], [part[2:-2]])
    else:
        return [part]

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

Попробуйте это с другими существующими определениями:

      >>> list(patterns(tokenize(template)))
['can you give me something please', 'can you give me something ASAP', 'would you give me something please', 'would you give me something ASAP', 'please give me something please', 'please give me something ASAP']

Обобщатьpatternsправильно, а не в зависимости от других глобальных функцийcombineиcandidates, мы должны использовать внедрение зависимостей — просто передавая их в качестве параметров, которые являются функциями более высокого порядка . Таким образом:

      from itertools import product

def patterns(data, candidates, combine):
    all_candidates = [candidates(element) for element in data]
    for result in product(*all_candidates):
        yield combine(result)

Теперь один и тот же основной код решает любую проблему. Примеры могут выглядеть так:

      def euler_51(s):
    for pattern in patterns(
        s,
        lambda letter: ['x', '5'] if letter == 'x' else [letter],
        ''.join
    ):
        print(pattern)

euler_51('1xxx1')

или

      def replace_in_template(template, replacement_lookup):
    tokens = re.split(r'(\(\(.*?\)\))', template)
    return list(patterns(
        tokens, 
        lambda part: (
            keywords.get(part[2:-2], [part[2:-2]])
            if part.startswith('((') and part.endswith('))')
            else [part]
        ),
        ''.join
    ))

replace_in_template(
    '((wouldyou)) give me something ((please))',
    {
        'wouldyou': ["can you", "would you", "please"],
        'please': ["please", "ASAP"]
    }
)