求2个允许字符生成长度为3的所有可能字符序列的算法

需求说明 #

需要生成由给定2个允许字符组成的、长度为3的所有可能字符序列，输入参数如下：

• 允许字符集合：caractersAllowed[2] = ['A', 'B']
• 目标序列长度：3，初始占位数组为sequenceTable[3] = [0,0,0]

原需求给出的预期输出共7项，实际全组合共8项，缺少合法项[B,B,A]。

实现逻辑 #

该需求本质是求允许字符集合的3次笛卡尔积，用递归实现适配性更强，可自由调整目标序列长度和允许字符数量：

1. 递归终止条件：当前拼接的序列长度等于目标长度，输出序列
2. 每层递归遍历所有允许字符，拼接到当前序列后进入下一层递归

代码实现（Python） #

def generate_all_sequences(allowed_chars, target_len, cur_seq=None):
    if cur_seq is None:
        cur_seq = []
    if len(cur_seq) == target_len:
        print(cur_seq)
        return
    for c in allowed_chars:
        generate_all_sequences(allowed_chars, target_len, cur_seq + [c])

# 代入参数调用
caractersAllowed = ['A', 'B']
sequence_length = 3
generate_all_sequences(caractersAllowed, sequence_length)

最终输出 #

运行代码后得到所有8个合法序列：

• ['A', 'A', 'A']
• ['A', 'A', 'B']
• ['A', 'B', 'A']
• ['A', 'B', 'B']
• ['B', 'A', 'A']
• ['B', 'A', 'B']
• ['B', 'B', 'A']
• ['B', 'B', 'B']

内容的提问来源于stack exchange，提问作者Gregory Pellegrin