如何高效生成元素可指定重复次数的排列？求最优实现方案

现成函数方案 #

如果可以使用第三方库，more_itertools中的distinct_permutations就是专门解决这个需求的工具，它会直接生成所有不重复的排列，彻底避免先生成全量排列再去重的低效操作。

用法示例：

from more_itertools import distinct_permutations

data = {1:3, 2:1, 3:2}
# 展开为带重复的元素列表
elements = []
for num, count in data.items():
    elements.extend([num]*count)

# 生成所有唯一排列
result = list(distinct_permutations(elements))

在高重复率场景（比如27个True+1个False）下，这个方法的效率和你实现的双元素函数一致，只会生成实际存在的唯一排列。

标准库原生高效实现 #

如果不想依赖第三方库，可以基于组合选择位置的思路扩展你的双元素解法，核心是递归地为每个元素选择放置位置，从根源上避免生成重复排列：

import itertools

def distinct_multiset_permutations(counts):
    # 整理元素与对应数量的列表，例如[(1,3), (2,1), (3,2)]
    elements = list(counts.items())
    total_length = sum(c for _, c in elements)
    
    def helper(remaining_elements, remaining_positions):
        if not remaining_elements:
            yield []
            return
        current_num, current_count = remaining_elements[0]
        # 从剩余位置中选择current_count个位置放置当前元素
        for positions in itertools.combinations(remaining_positions, current_count):
            perm = [None]*total_length
            for pos in positions:
                perm[pos] = current_num
            # 筛选出剩余位置，留给后续元素
            remaining_pos = [p for p in remaining_positions if p not in positions]
            # 递归处理剩余元素，填充空位置
            for sub_perm in helper(remaining_elements[1:], remaining_pos):
                for idx, num in zip(remaining_pos, sub_perm):
                    perm[idx] = num
                yield perm
    
    return list(helper(elements, list(range(total_length))))

# 测试示例
data = {1:3, 2:1, 3:2}
result = distinct_multiset_permutations(data)

效率优势说明 #

这个思路和你处理双元素的逻辑一致：只选择每个元素的放置位置，而非生成所有可能排列再去重。比如27个True+1个False的场景，只会生成C(28,1)=28种结果，完全不会产生冗余计算。

相比你原来的permutations+set方法，它的时间复杂度等于实际唯一排列的数量，而不是全排列的数量（后者在高重复场景下是天文数字级别的冗余）。

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