递归生成字符集字符串组合，需限制结果长度不超过n的问题

我编写了如下递归代码来生成字符串的所有组合：

def gen_recur(chr_lst, length, n , s, ls):
    
    if (n == 0):
        ls.append(s)
        return

    for j in range(0, length):
        str_app = s + chr_lst[j]
        gen_recur(chr_lst, length, n-1, str_app, ls)
    return

def generate_passwords(chr_str, length, ls):
    chr_lst = [char for char in chr_str]
    s = ""
    for n in range(1, length + 1):
        gen_recur(chr_lst, length, n, s, ls)

if __name__ == "__main__":
    chr_str = 'abc'
    length = len(chr_str)
    ls = []
    generate_passwords(chr_str, length, ls)
    print(ls)

但我希望仅生成长度≤n的字符串。例如，当字符集为'abc'、n=2时，当前输出包含所有长度1、2、3的组合：

['a', 'b', 'c', 'aa', 'ab', 'ac', 'ba', 'bb', 'bc', 'ca', 'cb', 'cc', 'aaa', 'aab', 'aac', 'aba', 'abb', 'abc', 'aca', 'acb', 'acc', 'baa', 'bab', 'bac', 'bba', 'bbb', 'bbc', 'bca', 'bcb', 'bcc', 'caa', 'cab', 'cac', 'cba', 'cbb', 'cbc', 'cca', 'ccb', 'ccc']

而理想输出应为长度≤2的组合：

['a', 'b', 'c', 'aa', 'ab', 'ac', 'ba', 'bb', 'bc', 'ca', 'cb', 'cc']

若将length参数改为2，输出会截断字符集（仅使用'a'、'b'）：

['a', 'b', 'aa', 'ab', 'ba', 'bb']

改为4则会触发列表索引越界错误。请帮忙修改代码，实现生成指定字符集下长度≤n的所有字符串组合的需求。

问题核心是你把字符集长度和目标最大字符串长度两个概念用同一个length参数混淆了，导致参数冲突，要么生成超出长度的组合，要么截断字符集或触发索引错误。

修改思路 #

• 拆分参数：明确区分字符集（直接用列表遍历避免索引操作）和目标最大长度max_len
• 调整递归逻辑：让递归自动覆盖从1到max_len的所有长度组合
• 移除冗余循环：递归内部完成长度递增的逻辑，无需外部循环

修改后的代码 #

def gen_recur(chr_lst, current_len, max_len, s, ls):
    # 非空字符串直接加入结果（覆盖1到max_len的所有长度）
    if len(s) > 0:
        ls.append(s)
    # 当前长度达到最大值时停止递归
    if current_len == max_len:
        return
    
    for char in chr_lst:
        gen_recur(chr_lst, current_len + 1, max_len, s + char, ls)

def generate_passwords(chr_str, max_len, ls):
    chr_lst = list(chr_str)
    gen_recur(chr_lst, 0, max_len, "", ls)

if __name__ == "__main__":
    chr_str = 'abc'
    max_len = 2  # 指定生成字符串的最大长度
    ls = []
    generate_passwords(chr_str, max_len, ls)
    # 按长度+字典序排序，匹配理想输出顺序
    ls.sort(key=lambda x: (len(x), x))
    print(ls)

代码说明 #

1. gen_recur函数：
   • chr_lst：字符集列表，直接遍历每个字符避免索引越界
   • current_len：当前递归生成的字符串长度
   • max_len：允许的最大字符串长度
   • 每次递归先将非空字符串加入结果，未达最大长度时继续拼接字符递归
2. 排序处理：
   • 若需要和理想输出的顺序（先所有长度1，再所有长度2）一致，通过sort方法按长度+字典序排序即可

测试输出 #

当chr_str='abc'、max_len=2时，输出：

['a', 'b', 'c', 'aa', 'ab', 'ac', 'ba', 'bb', 'bc', 'ca', 'cb', 'cc']

内容的提问来源于stack exchange，提问作者Chandler Cree