如何用itertools生成含重复元素列表的唯一全排列？

当列表包含重复元素时，itertools.permutations无法自动去重，会生成大量重复的排列结果。比如运行以下代码：

import itertools
for j in itertools.permutations([0,1,1]):
    print(j)

会得到6个结果，其中包含重复项：

(0, 1, 1)
(0, 1, 1)
(1, 0, 1)
(1, 1, 0)
(1, 0, 1)
(1, 1, 0)

但我们实际只需要3个唯一排列。

朴素解决方案的局限性 #

• 可以通过记录已生成的排列并手动去重，但这种方式需要额外存储空间，效率一般。
• 使用itertools.product结合过滤条件（比如元素和、计数等）也能得到结果：

import itertools
for j in itertools.product([0,1], repeat=3):
    if sum(j) != 2:
        continue
    print(j)

输出符合预期：

(0, 1, 1)
(1, 0, 1)
(1, 1, 0)

但这种方法在处理更大的列表时，会生成大量无效排列再过滤，时间复杂度极高，完全不实用。

基于标准库的高效原生实现 #

要在itertools生态下高效生成唯一排列，可以结合元素计数和组合选择的思路：

针对特定场景的简化实现

以[0,1,1]为例，我们可以通过itertools.combinations确定重复元素的位置，直接生成唯一排列：

import itertools
lst = [0,1,1]
# 统计元素出现次数
element_counts = {0:1, 1:2}
n = len(lst)

# 选择放置0的位置，剩下的位置放1
for zero_positions in itertools.combinations(range(n), element_counts[0]):
    perm = [1]*n
    for pos in zero_positions:
        perm[pos] = 0
    print(tuple(perm))

输出：

(0, 1, 1)
(1, 0, 1)
(1, 1, 0)

通用化的唯一排列生成器

如果要处理任意含重复元素的列表，可以结合回溯法和collections.Counter实现，避免生成重复排列：

import itertools
from collections import Counter

def unique_permutations(lst):
    counter = Counter(lst)
    elements = list(counter.keys())
    counts = list(counter.values())
    total_length = len(lst)

    def backtrack(current, remaining_counts):
        if len(current) == total_length:
            yield tuple(current)
            return
        for idx in range(len(elements)):
            if remaining_counts[idx] == 0:
                continue
            # 跳过与前一个元素相同且前一个元素还有剩余的情况，避免重复排列
            if idx > 0 and elements[idx] == elements[idx-1] and remaining_counts[idx-1] > 0:
                continue
            # 选择当前元素
            remaining_counts[idx] -= 1
            current.append(elements[idx])
            yield from backtrack(current, remaining_counts)
            # 回溯
            current.pop()
            remaining_counts[idx] += 1

    yield from backtrack([], counts.copy())

# 测试示例
for perm in unique_permutations([0,1,1]):
    print(perm)

这个方法直接基于元素的计数生成排列，不会产生重复结果，效率远高于过滤法。

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