通过更改字符串中的3个或多个位置进行组合

Question

下面的代码接受一个字符串，然后在p =中，每个可以更改的索引都有一个映射，映射的字符是什么。例如d1位于p[0]，因此字符a（位于string[0]）可以替换为d或1。一次必须更改的字符数限制为3

from itertools import combinations, product

string = "abc123" 

p = ["d1", "c3", "", "", "0", "56"]

d = {idx: (v if string[idx] in v else string[idx]+v) for idx, v in enumerate(p)} 

all_of_em = (''.join(whatever) for whatever in product(*d.values()))

fewer = [w for w in all_of_em if sum(a != b for a, b in zip(w, string)) == 3]

with open("list.txt","w") as f: 
    for w in fewer: 
        f.write(w+"\n")

作为上述代码的结果，如果我们在p中用指定的替代字符更改字符串中的3个位置，我们将找到所有可能的组合

acc105
acc106
a3c105
a3c106
dbc105
dbc106
dcc125
dcc126
dcc103
d3c125
d3c126
d3c103
1bc105
1bc106
1cc125
1cc126
1cc103
13c125
13c126
13c103

目标是更快地打印结果，例如，这些行应该更改我认为：

with open("list.txt","w") as f: 
    for w in fewer: 
        f.write(w+"\n")

因此，输出将保存为python3 py.py >> list.txt

将乐于从您的解决方案中学习

Answer 1

您的解决方案基于蛮力方法。您正在生成所有可能的备选字符串，然后筛选出那些不符合仅3个更改条件的字符串。更好的方法是只考虑那些符合标准的组合。我将忽略保存到文件的部分，因为这两种解决方案都是相同的。更快的解决方案是：

def change_string(input_string, mapping, replace=3):
    input_string = list(input_string)

    to_replace = dict()
    for idx, replacement in enumerate(mapping):
        if not replacement: continue

        to_replace[idx] = replacement
        if input_string[idx] in replacement:
            to_replace[idx] = [char for char in replacement if char != mapping[idx]]

    for indices in combinations(to_replace, r=replace):
        for chars in product(*[to_replace[index] for index in indices]):
            temp = input_string[:]
            for index, char in zip(indices, chars):
                temp[index] = char
            yield ''.join(temp)

说明

我将输入字符串更改为列表，这样可以更快地进行替换，因为列表是可变的，而字符串不是可变的

然后我过滤映射（p），以仅表示将要更改的索引。这将删除所有空字符串，并为我提供必须查看的索引

to_replace = dict()
    for idx, replacement in enumerate(mapping):
        if not replacement: continue

        to_replace[idx] = replacement
        if input_string[idx] in replacement:
            to_replace[idx] = [char for char in replacement if char != mapping[idx]]

注意：我还确保映射中的值与原始字符串值不相等，这可能不是您想要的

然后，我创建了所有可能的具有所需长度的索引组合（replace=3）

for indices in combinations(to_replace, r=replace):

使用您的示例，这将包含以下一组索引：

(0, 1, 4)
(0, 1, 5)
(0, 4, 5)
(1, 4, 5)

然后，我从这些索引创建所有可能的character组合：

for chars in product(*[to_replace[index] for index in indices]):

例如，对于索引(0, 1, 4)或值('d1', 'c3', '0')：

('d', 'c', '0')
('d', '3', '0')
('1', 'c', '0')
('1', '3', '0')

所有的字符组合都产生了

然后我创建一个输入字符串的副本（注意它是一个列表，因此我们可以执行快速替换），并在正确的索引处替换字符

比较

• 你的职能

def OP(input_string, replace=3):
    p = ["d1", "c3", "", "", "0", "56"]
    d = {idx: (v if input_string[idx] in v else input_string[idx] + v) for idx, v in enumerate(p)}
    all_of_em = (''.join(whatever) for whatever in product(*d.values()))
    fewer = [w for w in all_of_em if sum(a != b for a, b in zip(w, input_string)) == replace]
    return fewer

更换is 3

print(timeit.timeit("OP('abc123')", setup="from __main__ import OP", number=100_000))
# 5.6281933 seconds

print(timeit.timeit("list(change_string('abc123', ['d1', 'c3', '', '', '0', '56']))",
                    setup="from __main__ import change_string", number=100_000))
# 1.3682368 seconds

这大约是3倍的速度，现在有趣的部分是看看如果我们将替换值增加到4会发生什么

更换is 4

print(timeit.timeit("OP('abc123', replace=4)", setup="from __main__ import OP", number=100_000))
# 5.5450302 seconds

print(timeit.timeit("list(change_string('abc123', ['d1', 'c3', '', '', '0', '56'], replace=4))",
                    setup="from __main__ import change_string", number=100_000))
# 0.6179974 seconds

由于我的解决方案只需检查几个组合，发出的呼啸声要快9倍

使用replace is2或1也可以看到类似的增长

Answer 2

使用生成器函数可以避免在内存中创建和操作大型列表。您可以使用join将其作为单个文本块写入文件

def replace(S,R,N):
    if not N: yield S; return
    for i,chars in enumerate(R[:(1-N) or None]):
        for c in chars:
            yield from (S[:i]+c+s for s in replace(S[i+1:],R[i+1:],N-1))
            
def writeReplace(S,R,N):
    with open("list.txt","w") as f: 
        f.write("\n".join(replace(S,R,3)))

S = "abc123" 
R = ["d1", "c3", "", "", "0", "56"]
writeReplace(S,R,3)

dcc103
dcc125
dcc126
d3c103
d3c125
d3c126
dbc105
dbc106
1cc103
1cc125
1cc126
13c103
13c125
13c126
1bc105
1bc106
acc105
acc106
a3c105
a3c106

这大约快了2.5倍