我创建了一个脚本，该脚本使用以下代码迭代s字符字符串中的所有字符组合：
sCharacters = "abcdefghijklmnopqrstuvwxyz0123456789"
iKeyLength = len(sCharacters)
for sCharacterCombination in itertools.product(sCharacters, repeat=iKeyLength):
# Do Stuff Here
然而，我只对在sCharacterComposition中单个字符的表示次数不超过n次的组合感兴趣。例如；我想过滤掉字符串aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab，只得到这样的7efad3ca411bf57f1df57c0b4e9282aa
我试着只检查每个sCharacterCombination，但这不好，因为我仍然需要迭代大量我永远不会使用的项目。
我如何让迭代器根据每个项目创建列表，其中没有一个字符首先表示超过n次，这样我就不必迭代我不会使用的项目了？
如果我能说：，那就太棒了
- 单个字符可以在sCharacterComposition中表示的最大次数
- 单个字符在一行中可以表示的最大次数
这允许我说一个字符最多可以在sCharacterComposition中出现四次，但它在一行中不能超过两次。例如，这是可以的1121...，但这不是1112...。
谢谢你抽出时间。
以下是一些比当前方法更高效的代码。
首先，我们使用itertool的combinations_with_replacement函数来创建所需长度的组合，过滤掉重复次数超过所需次数的组合。然后我们排列每个组合；我使用的排列算法(由14世纪印度数学家Narayana Pandita创建)能够正确处理重复，这与itertools中的算法不同。然后，我们使用itertool的groupby来过滤包含超过允许游程长度的相同字符的游程的排列。
我包含了两个函数：permutations_with_limited_repetition限制相同字符的游程长度；permutations_with_repetition没有。
请注意，输入序列必须从低到高排序，否则此算法将无法正确运行。
from itertools import combinations_with_replacement, groupby
def lexico_permute(a):
a = list(a)
yield a
n = len(a) - 1
while True:
for j in range(n-1, -1, -1):
if a[j] < a[j + 1]:
break
else:
return
v = a[j]
for k in range(n, j, -1):
if v < a[k]:
break
a[j], a[k] = a[k], a[j]
a[j+1:] = a[j+1:][::-1]
yield a
def permutations_with_repetition(seq, length, maxrepeat):
for combo in combinations_with_replacement(seq, length):
if any(combo.count(c) > maxrepeat for c in combo):
continue
yield from lexico_permute(combo)
def permutations_with_limited_repetition(seq, length, maxrepeat, maxrun):
for combo in combinations_with_replacement(seq, length):
if any(combo.count(c) > maxrepeat for c in combo):
continue
for perm in lexico_permute(combo):
if any(len(list(g)) > maxrun for _, g in groupby(perm)):
continue
yield perm
# Test
src = list('abcde')
for lst in permutations_with_limited_repetition(src, 3, 2, 1):
print(''.join(lst))
输出
aba
aca
ada
aea
bab
abc
acb
bac
bca
cab
cba
abd
adb
bad
bda
dab
dba
abe
aeb
bae
bea
eab
eba
cac
acd
adc
cad
cda
dac
dca
ace
aec
cae
cea
eac
eca
dad
ade
aed
dae
dea
ead
eda
eae
bcb
bdb
beb
cbc
bcd
bdc
cbd
cdb
dbc
dcb
bce
bec
cbe
ceb
ebc
ecb
dbd
bde
bed
dbe
deb
ebd
edb
ebe
cdc
cec
dcd
cde
ced
dce
dec
ecd
edc
ece
ded
ede
关于置换算法的注释(非生成器)版本，请参阅我去年写的这个答案。
更新
第一个过滤器
if any(combo.count(c) > maxrepeat for c in combo):
可以通过使用与第二滤波器相同的CCD_ 11技术来提高效率：
if any(len(list(g)) > maxrepeat for _, g in groupby(combo)):
(我昨天应该有这个想法，但我本来不打算做第二个滤镜，这是最后一刻的灵感)。