Optionally replacing a substring python

Question

My list of replacement is in the following format.

lstrep = [('A',('aa','aA','Aa','AA')),('I',('ii','iI','Ii','II')),.....]

What I want to achieve is optionally change the occurrence of the letter by all the possible replacements. The input word should also be a member of the list. e.g.

input - DArA

Expected output -

['DArA','DaarA','Daaraa','DAraa','DaArA','DAraA','DaAraA','DAarA','DAarAa', 'DArAa','DAArA','DAArAA','DArAA']

My try was

lstrep = [('A',('aa','aA','Aa','AA'))]
def alte(word,lstrep):
    output = [word]
    for (a,b) in lstrep:
        for bb in b:
            output.append(word.replace(a,bb))
    return output
print alte('DArA',lstrep)

The output I received was ['DArA', 'Daaraa', 'DaAraA', 'DAarAa', 'DAArAA'] i.e. All occurrences of 'A' were replaced by 'aa','aA','Aa' and 'AA' respectively. What I want is that it should give all permutations of optional replacements.

score 3 · Accepted Answer · answered Dec 05 '15 at 18:37

itertools.product will give all of the permutations. You can build up a list of substitutions and then let it handle the permutations.

import itertools

lstrep = [('A',('aa','aA','Aa','AA')),('I',('ii','iI','Ii','II'))]
input_str = 'DArA'

# make substitution list a dict for easy lookup
lstrep_map = dict(lstrep)

# a substitution is an index plus a string to substitute. build
# list of subs [[(index1, sub1), (index1, sub2)], ...] for all
# characters in lstrep_map.
subs = []
for i, c in enumerate(input_str):
    if c in lstrep_map:
        subs.append([(i, sub) for sub in lstrep_map[c]])

# build output by applying each sub recorded
out = [input_str]
for sub in itertools.product(*subs):
    # make input a list for easy substitution
    input_list = list(input_str)
    for i, cc in sub:
        input_list[i] = cc
    out.append(''.join(input_list))

print(out)

Lovely. It made my day. Absolutely native and fast. – Dhaval Patel Dec 06 '15 at 02:23 — Dhaval Patel, Dec 06 '15 at 02:23

score 0 · Answer 2 · edited Jun 20 '20 at 09:12

Try constructing tuples of all possible permutations based on the replaceable characters that occur. This will have to be achieved using recursion.

The reason recursion is necessary is that you would need a variable number of loops to achieve this.

For your example "DArA" (2 replaceable characters, "A" and "A"):

replaceSet = set()
replacements = ['A':('aa','aA','Aa','AA'),'I':('ii','iI','Ii','II'),.....]
for replacement1 in replacements["A"]:
    for replacement2 in replacements["A"]:
        replaceSet.add((replacement1, replacement2))

You see you need two loops for two replaceables, and n loops for n replaceables.

Think of a way you could use recursion to solve this problem. It will likely involve creating all permutations for a substring that contains n-1 replaceables (if you had n in your original string).

Optionally replacing a substring python

2 Answers2

For your example "DArA" (2 replaceable characters, "A" and "A"):

Linked