Python - создать новую строку определенной длины с n заменами из определенного алфавита

Я работал над быстрым и эффективным способом решения следующей проблемы, но до сих пор мне удавалось решить ее только с помощью довольно медленного решения с использованием петли. В любом случае, вот описание:

Итак, у меня есть строка длиной L, скажем 'BBBX', Я хочу найти все возможные строки длины L, начиная с 'BBBX', которые отличаются максимум на 2 позиции и, как минимум, на 0 позиций. Кроме того, при построении новых строк новые символы должны быть выбраны из определенного алфавита.

Я думаю, что размер алфавита не имеет значения, поэтому давайте скажем, что в этом случае алфавит ['B', 'G', 'C', 'X'],

Таким образом, некоторые примеры выходных данных будут, 'BGBG', 'BGBC', 'BBGX'и т. д. Для этого примера со строкой длиной 4 с до 2 подстановками мой алгоритм находит 67 возможных новых строк.

Я пытался использовать itertools чтобы решить эту проблему, но мне трудно найти решение. Я пытаюсь использовать itertools.combinations(range(4), 2) найти все возможные позиции. Я тогда думаю об использовании product() от itertools построить все возможности, но я не уверен, есть ли способ, которым я мог бы как-то связать его с показателями из вывода combinations(),

Источник

2 ответа

Решение

Вот мое решение.

Первый цикл for сообщает нам, сколько замен мы будем выполнять. (0, 1 или 2 - мы проходим каждый)

Второй цикл сообщает нам, какие буквы мы будем менять (по их индексам).

Третий цикл проходит через все возможные изменения букв для этих индексов. Есть некоторая логика, чтобы убедиться, что мы действительно изменили букву (изменение "C" на "C" не считается).

import itertools

def generate_replacements(lo, hi, alphabet, text):
    for count in range(lo, hi + 1):
        for indexes in itertools.combinations(range(len(text)), count):
            for letters in itertools.product(alphabet, repeat=count):
                new_text = list(text)
                actual_count = 0
                for index, letter in zip(indexes, letters):
                    if new_text[index] == letter:
                        continue
                    new_text[index] = letter
                    actual_count += 1
                if actual_count == count:
                    yield ''.join(new_text)

for text in generate_replacements(0, 2, 'BGCX', 'BBBX'):
    print text

Вот его вывод:

BBBX GBBX CBBX XBBX BGBX BCBX BXBX BBGX BBCX BBXX BBBB BBBG BBBC GGBX
GCBX GXBX CGBX CCBX CXBX XGBX XCBX XXBX GBGX GBCX GBXX CBGX CBCX CBXX
XBGX XBCX XBXX GBBB GBBG GBBC CBBB CBBG CBBC XBBB XBBG XBBC BGGX BGCX
BGXX BCGX BCCX BCXX BXGX BXCX BXXX BGBB BGBG BGBC BCBB BCBG BCBC BXBB
BXBG BXBC BBGB BBGG BBGC BBCB BBCG BBCC BBXB BBXG BBXC
Источник

Не проверено много, но он находит 67 для примера, который вы дали. Простой способ связать индексы с продуктами через zip():

def sub(s, alphabet, minsubs, maxsubs):
    from itertools import combinations, product
    origs = list(s)
    alphabet = set(alphabet)
    for nsubs in range(minsubs, maxsubs + 1):
        for ix in combinations(range(len(s)), nsubs):
            prods = [alphabet - set(origs[i]) for i in ix]
            s = origs[:]
            for newchars in product(*prods):
                for i, char in zip(ix, newchars):
                    s[i] = char
                yield "".join(s)

count = 0
for s in sub('BBBX', 'BGCX', 0, 2):
    count += 1
    print s
print count

Примечание: главное отличие от FogleBird в том, что я отправил первым - LOL;-) Алгоритмы очень похожи. Шахта строит входы в product() так что никакая замена буквы для себя никогда не предпринимается; FogleBird's допускает "идентичную" замену, но подсчитывает, сколько допустимых замен сделано, и затем отбрасывает результат, если произошла какая-либо замена идентичности. Для более длинных слов и большого числа замен это может быть намного медленнее (потенциально разница между len(alphabet)**nsubs а также (len(alphabet)-1)**nsubs времена вокруг ... in product(): петля).

Источник
Другие вопросы по тегам