生成所有具有字符 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']

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

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

Generate all strings having characters a,b or c with length equal to n with atmost 1 b and 2 c

python

string

backtracking

python-3.x