使用atmost 1 b和atmost 2生成长度等于n的具有字符a、b或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']

Answer 1

你的一些逻辑是错误的；例如，countb<=1意味着您可能已经有了一个b，所以您不必再添加一个。另外，在该调用中，您将向countb和countc添加1

Answer 2

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

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