如何修改Heap算法以避免生成重复排列（含重复元素输入）

原Heap's算法在处理含重复元素的数组时，会因交换相同元素生成重复排列。要实现高效去重，核心是在交换前跳过重复元素的处理，从源头避免生成重复排列，无需额外存储已生成的排列。

修改后的代码 #

a = [0, 1, 2, 2, 3]
length = len(a)

def heapPermutation(a, size):
    if size == 1:
        print(a.copy())  # 打印副本避免后续修改影响输出结果
        return
    
    seen = set()  # 记录当前层已处理过的元素，避免重复交换
    for i in range(size):
        if a[i] in seen:
            continue  # 跳过已处理过的重复元素，避免生成重复排列
        seen.add(a[i])
        
        heapPermutation(a, size-1)
        
        # 根据size奇偶性执行交换操作
        if size % 2 == 1:
            a[0], a[size-1] = a[size-1], a[0]
        else:
            a[i], a[size-1] = a[size-1], a[i]

# 调用时传入原数组副本，避免修改原数组初始状态
heapPermutation(a.copy(), length)

关键改动说明 #

1. seen集合去重：在每一层递归的循环中，用集合记录已经处理过的元素。如果当前元素a[i]已在集合中，说明之前已经处理过相同元素的交换逻辑，直接跳过即可，从根源避免重复排列的生成。
2. 打印数组副本：由于Heap's算法是原地修改数组，直接打印a会导致后续交换操作修改已输出的结果，因此打印a.copy()来保留当前排列的快照。
3. 传入数组副本：如果需要保留原数组的初始状态，调用函数时传入原数组的副本，避免原数组被递归过程中的交换操作修改。

效果验证 #

• 输入[0,1,2,2]时，理论无重复排列数为4!/2! = 12，修改后的代码会输出12种不重复的排列。
• 输入[0,1,2,2,3]时，理论无重复排列数为5!/2! = 60，代码会输出60种不重复的排列。

这种方式的时间复杂度接近O(n!/k1!k2!...km!)（其中k1,k2...km是各重复元素的出现次数），和理论无重复排列数的计算量一致，效率远高于事后去重的方案。

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