Python实现：生成K个字母构成的长度为N的所有等价字母模式

你要找的这类「模式」是字符串的首次出现序规范化表示：同一等价类的所有字符串，都可以通过字符重命名映射到同一个标准串，规则是：字符串里第一次出现的新字符，按顺序用A、B、C……依次替换。比如BA第一个出现的字符是B，替换为A，后续出现的A是第二个新字符，替换为B，最终规范化结果就是AB，和你给出的等价判定规则完全匹配。

这类模式的计数规则和你给出的案例完全吻合：长度为N、最多用m个不同字符的模式总数等于第二类斯特林数前缀和$S(N,1)+S(N,2)+...+S(N,m)$，当K≥N时总数就是贝尔数$B_N$：

• N=2时贝尔数为2，对应K≥2时只有2种模式
• N=3时贝尔数为5，对应K≥3时共5种模式；K=2时总和为$S(3,1)+S(3,2)=1+3=4$，和你给出的案例完全一致。

不需要先生成全量排列/组合再去重，直接按规则构造符合要求的标准模式即可，时间复杂度和最终输出的模式总数线性相关，没有额外冗余计算。

def generate_patterns(N: int, K: int) -> list[str]:
    if N <= 0 or K <= 0:
        return []
    # 长度为N的串最多用到N个不同字符，超过N的K值不影响结果
    max_distinct = min(K, N)
    patterns = []

    # 回溯构造：current为当前已构造的串片段，distinct_cnt为当前已使用的不同字符数
    def backtrack(current: list[str], distinct_cnt: int):
        if len(current) == N:
            patterns.append(''.join(current))
            return
        # 优先尝试复用所有已经出现过的字符
        for char_idx in range(distinct_cnt):
            current.append(chr(ord('A') + char_idx))
            backtrack(current, distinct_cnt)
            current.pop()
        # 未达到可用字符上限时，尝试加入一个从未出现过的新字符
        if distinct_cnt < max_distinct:
            current.append(chr(ord('A') + distinct_cnt))
            backtrack(current, distinct_cnt + 1)
            current.pop()

    backtrack([], 0)
    return patterns

对应你给出的测试案例，运行结果完全匹配：

# K=3、N=2 输出：['AA', 'AB']
print(generate_patterns(2, 3))
# K=3、N=3 输出：['AAA', 'AAB', 'ABA', 'ABB', 'ABC']
print(generate_patterns(3, 3))
# K=2、N=3 输出：['AAA', 'AAB', 'ABA', 'ABB']
print(generate_patterns(3, 2))

如果需要输出数字编码而非字母形式，只需要修改代码里的字符拼接逻辑即可，核心构造流程不需要改动。

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