如何高效生成含重复元素的Python唯一排列？

你当前用itertools.permutations()加去重的方式效率极低，核心原因是全排列的数量是(x+z)!，而实际唯一排列的数量仅为组合数C(x+z, x)，两者差距巨大（比如16个元素、7个a9个b的场景，全排列约2e13个，唯一排列仅11440个），去重过程完全是做无用功。

高效实现思路 #

直接通过选择a的放置位置来生成唯一排列：从总长度x+z的位置中选出x个位置放a，剩下的位置自动放b，全程不会产生重复排列。

代码实现 #

import itertools

def unique_ab_permutations(count_a, count_b, elem_a='item a', elem_b='item b'):
    total_length = count_a + count_b
    # 遍历所有放置elem_a的位置组合
    for a_positions in itertools.combinations(range(total_length), count_a):
        permutation = [elem_b] * total_length
        for pos in a_positions:
            permutation[pos] = elem_a
        yield tuple(permutation)  # 若需要列表形式，直接返回permutation即可

为什么这个方法高效 #

• 时间复杂度直接对应唯一排列的数量，即组合数C(x+z, x)，无需额外去重操作
• 内存占用低，无需存储已生成的排列做查重对比
• 对于你提到的16元素场景，仅需生成11440个排列，执行速度会有质的提升

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