Skip to main content
 首页 » 编程设计

python之如何创建一个迭代器来生成项目,其中没有项目的单个字符在 python 中表示超过 n 次

2025年04月02日16飞鱼

我创建了一个脚本,它使用以下代码迭代 sCharacters 字符串中的所有字符组合:

sCharacters = "abcdefghijklmnopqrstuvwxyz0123456789" 
iKeyLength = len(sCharacters) 
 
for sCharacterCombination in itertools.product(sCharacters, repeat=iKeyLength): 
    # Do Stuff Here 

然而,我只对在 sCharacterCombination 中没有单个字符出现超过 n 次的组合感兴趣。 例如;我想过滤掉像这样的字符串 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaab 并且只得到像 7efad3ca411bf57f1df57c0b4e9282aa

我尝试只检查每个 sCharacterCombination,但这并不好,因为我仍然必须遍历一堆我永远不会使用的项目。

我怎样才能让迭代器基于每个项目创建列表,每个项目没有单个字符首先表示超过 n 次,这样我就不必迭代项目我不会用?

如果我能说,那就太棒了:

  • 单个字符可以在 sCharacterCombination 中表示的最大次数。
  • 单个字符可以在一行中表示的最大次数。

这样我就可以说单个字符最多可以在 sCharacterCombination 中出现四次,但连续出现的次数不能超过两次。例如。这没问题 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 

有关排列算法的注释(非生成器)版本,请参阅 this answer我去年写的。


更新

第一个过滤器

if any(combo.count(c) > maxrepeat for c in combo): 

可以通过使用与第二个过滤器相同的 groupby 技术来提高效率:

if any(len(list(g)) > maxrepeat for _, g in groupby(combo)): 

(我应该昨天就想到了,但我原本不打算做第二个过滤器,这是最后一刻的灵感)。