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

Question

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

Итак, у меня есть строка длины 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().

Answer 1

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

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

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

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

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 

Answer 2

Не тестировалось много, но он нашел 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 ;-) Алгоритмы очень похожи. Mine создает входные данные для product(), так что никакая замена буквы для себя никогда не предпринимается; FogleBird разрешает «идентификационные» замены, но подсчитывает, сколько действительных замещений сделано, а затем удаляет результат, если произошли какие-либо подстановки идентичности. При более длинных словах и большем числе замещений может быть намного медленнее (потенциально разница между len(alphabet)**nsubs и (len(alphabet)-1)**nsubs раз вокруг цикла ... in product():).