python - 生成具有字符 a、b 或 c 且长度等于 n 且最多 1 b 和 2 c 的所有字符串

Question

生成具有以下约束的所有字符串

• 长度：n
• 允许的字符：a,b,c
• 最多一个 b
• 最多两个c

我写了以下代码

def generate(s,counta,countb,countc,n,result):
    if counta+countb+countc==n:
        print(counta,countb,countc)
        result.append(s)
        print(s)
        return
    if counta+countb+countc<n and counta<=n:
        generate(s+"a",counta+1,countb,countc,n,result)
    if counta+countb+countc<n and countb<=1:
        generate(s+"b",counta+1,countb+1,countc,n,result)
    if counta+countb+countc<n and countc<=2:
        generate(s+"c",counta,countb,countc+1,n,result)


result=[]
generate("",0,0,0,3,result)
print(result)

我得到以下结果，我不明白为什么。一些长度小于 n 的字符串被添加到结果中。

['aaa', 'aac', 'ab', 'aca', 'acc', 'ba', 'bc', 'caa', 'cac', 'cb', 'cca', 'ccc']

更新代码：（工作）

def generate(s,counta,countb,countc,n,result):
if counta+countb+countc==n:
    # print(counta,countb,countc)
    result.append(s)
    # print(s)
    return
if counta+countb+countc<n and counta<=n:
    generate(s+"a",counta+1,countb,countc,n,result)
if counta+countb+countc<n and countb<1:
    generate(s+"b",counta,countb+1,countc,n,result)
if counta+countb+countc<n and countc<2:
    generate(s+"c",counta,countb,countc+1,n,result)

result=[]
generate("",0,0,0,3,result)
print(result)

输出：

['aaa', 'aab', 'aac', 'aba', 'abc', 'aca', 'acb', 'acc', 'baa', 'bac', 'bca', 'bcc', 'caa', 'cab', 'cac', 'cba', 'cbc', 'cca', 'ccb']

标签： pythonpython-3.xstringbacktracking

Answer 1

如果您更喜欢更清洁的解决方案，那么下面的代码应该可以完成这项工作。约束逻辑与生成逻辑完全分离。这样，可以独立于生成逻辑添加约束。

from itertools import product

n = 3

for i in map(''.join, product('abc', repeat=n)):
    if i.count('b') <= 1 and i.count('c') <= 2:
        print(i)

输出：

aaa
aab
aac
aba
abc
aca
acb
acc
baa
bac
bca
bcc
caa
cab
cac
cba
cbc
cca
ccb