可选地替换子字符串

Question

我的替换名单如下。你知道吗

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

我想要实现的是通过所有可能的替换来选择性地更改字母的出现。输入的单词也应该是列表的一个成员。 e、 g

输入-DArA

预期输出-

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

我的尝试是

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)

我收到的输出是['DArA', 'Daaraa', 'DaAraA', 'DAarAa', 'DAArAA']，即所有出现的'A'分别被'aa'、'aa'、'aa'和'aa'替换。我想要的是它应该给出所有可选替换的排列。你知道吗

Answer 1

itertools.product将给出所有的排列。您可以建立一个替换列表，然后让它处理排列。你知道吗

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)

Answer 2

尝试根据出现的可替换字符构造所有可能排列的元组。这必须使用递归来实现。你知道吗

递归之所以是必要的，是因为您需要可变数量的循环来实现这一点。你知道吗

例如“DArA”（2个可替换字符，“A”和“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))

您可以看到，对于两个可替换项需要两个循环，对于n可替换项需要n循环。你知道吗

---

想办法用递归来解决这个问题。它可能涉及为包含n-1可替换项的子串创建所有置换（如果原始字符串中有n）。你知道吗