Geek Answers Handbook

Python - create a new string of a certain length with n substitutions from a specific alphabet

I am working on a quick and effective way to solve the next problem, but so far I have been able to solve it using a rather slow solution to solve the socket problem. Anyway, here is the description:

So, I have a string of length L, say 'BBBX'. I want to find all possible lines of length L, starting with 'BBBX', that differ by no more than 2 positions and at least 0 positions. In addition, when creating new lines, new characters must be selected from a specific alphabet.

I assume that the size of the alphabet does not matter, so let's say the alphabet in this case ['B', 'G', 'C', 'X'].

So, some rough conclusion would be, 'BGBG', 'BGBC', 'BBGX', etc. For this example, with a line length of 4 s to two permutations, my algorithm will find 67 possible new lines.

I am trying to use itertoolsto solve this problem, but it is difficult for me to find a solution. I try to use itertools.combinations(range(4), 2)to find all possible positions. Then I think about using product()out itertoolsto build all the features, but I'm not sure if there is a way to relate it somehow to the indices from the output combinations().

+4
source share
2 answers

Here is my solution.

The first cycle of the cycle tells us how many replacements we will perform. (0, 1 or 2 - we go through each)

, ( ).

. , , ( "" "" ).

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
+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():).

+1

More articles:


All Articles