通过更改字符串中 3 个或更多位置的组合
Combinations by changing 3 or more places in a string
下面的代码采用一个字符串，然后在 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
将乐于从您的解决方案中学习。
使用生成器函数将避免在内存中创建和操作大型列表。您可以使用 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 倍。
您的解决方案基于蛮力方法。您正在生成所有可能的替代字符串，然后过滤掉不符合仅 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]]
注意：我还要确保映射中的值不等于原始字符串值，这可能不是您想要的。
然后我创建所有可能的具有所需长度的索引组合（替换=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
替换为 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 会发生什么
替换为 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 倍，因为我的解决方案只需要检查几个组合。
使用替换可以看到类似的增加是 2 或 1。
下面的代码采用一个字符串，然后在 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.
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
将乐于从您的解决方案中学习。
使用生成器函数将避免在内存中创建和操作大型列表。您可以使用 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 倍。
您的解决方案基于蛮力方法。您正在生成所有可能的替代字符串，然后过滤掉不符合仅 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]]
注意：我还要确保映射中的值不等于原始字符串值，这可能不是您想要的。
然后我创建所有可能的具有所需长度的索引组合（替换=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
替换为 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 会发生什么
替换为 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 倍，因为我的解决方案只需要检查几个组合。
使用替换可以看到类似的增加是 2 或 1。