如何用Python高效生成'AABBBCCCCCDDDDDEEEEE'的无重复全排列？

问题描述 #

需要生成序列'AABBBCCCCCDDDDDEEEEE'的无重复全排列，当前使用的代码如下：

from itertools import permutations
import pandas as pd

df = pd.DataFrame()
for s in permutations('AABBBCCCCCDDDDDEEEEE'):
    df.loc[len(df)] = s
    if len(df) % 1000 == 0:
        df = df.drop_duplicates(ignore_index=True)

但该方法速度极慢，询问Python中是否有高效实现方式。

核心问题分析 #

你当前方法效率低的根源是itertools.permutations会生成所有重复排列——原序列总长度22，其中A出现2次，B出现3次，C、D、E各出现5次，理论无重复排列数为22!/(2!×3!×5!×5!×5!)（约1.06×10¹²个），但permutations会生成22!个元素（这个数字远超万亿级），后续再去重完全是在做无用功，浪费大量算力和内存。

高效实现方案 #

方案一：使用第三方库more_itertools.distinct_permutations #

more_itertools库中的distinct_permutations专门针对含重复元素的场景优化，内部直接生成无重复的排列，无需事后去重：

from more_itertools import distinct_permutations
import pandas as pd

seq = 'AABBBCCCCCDDDDDEEEEE'
# 直接生成无重复排列并转为DataFrame（注意：排列数量极大，内存可能无法承载）
df = pd.DataFrame(distinct_permutations(seq))

如果内存不足，建议迭代处理单个排列，避免一次性加载所有结果：

from more_itertools import distinct_permutations

seq = 'AABBBCCCCCDDDDDEEEEE'
for idx, perm in enumerate(distinct_permutations(seq)):
    # 此处替换为单个排列的处理逻辑，比如写入文件/数据库
    if idx % 1000 == 0:
        print(f"已处理{idx}个排列")

方案二：手动实现回溯法生成无重复排列 #

若不想依赖第三方库，可以自己编写回溯算法，在生成过程中跳过重复元素，从源头避免重复排列：

import pandas as pd

def distinct_permutations(seq):
    seq_sorted = sorted(seq)
    n = len(seq_sorted)
    used = [False] * n
    result = []
    
    def backtrack(current):
        if len(current) == n:
            result.append(tuple(current))
            return
        for i in range(n):
            if used[i]:
                continue
            # 跳过同一层的重复元素，避免生成重复排列
            if i > 0 and seq_sorted[i] == seq_sorted[i-1] and not used[i-1]:
                continue
            used[i] = True
            current.append(seq_sorted[i])
            backtrack(current)
            used[i] = False
            current.pop()
    
    backtrack([])
    return result

seq = 'AABBBCCCCCDDDDDEEEEE'
perms = distinct_permutations(seq)
df = pd.DataFrame(perms)

重要提示 #

无论使用哪种方法，该序列的无重复排列数量都达到万亿级，无法全部存入内存，建议根据实际需求做分批持久化处理（比如写入磁盘文件），而不是尝试存入DataFrame中。

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