使用for循环时如何高效检查重复值？求18长度唯一排列优化方案

我需要获取以下列表的所有唯一排列，要生成长度为18的排列。直接用itertools.permutations再去重会导致电脑崩溃，我试过添加前检查唯一性，但生成6或7长度的排列都要40秒，完全没法处理18长度的情况。有没有更高效的实现方式？

原代码：

pos = ['QB', 'QB', 'QB',
       'RB', 'RB', 'RB', 'RB', 'RB', 'RB', 'RB', 'RB', 'RB', 'RB', 'RB',
       'WR', 'WR', 'WR', 'WR', 'WR', 'WR', 'WR', 'WR', 'WR', 'WR', 'WR',
       'TE', 'TE', 'TE', 'TE', 'TE']

combos = set()

for combo in itertools.permutations(pos, 18):
    if combo not in combos:
        combos.add(combo)

解决方案：避免生成重复排列，直接构造唯一结果 #

你的核心问题是itertools.permutations会生成大量重复项，事后去重的时间和空间成本完全不可控。正确思路是在生成过程中就跳过重复排列，或者基于元素计数直接构造唯一排列。

方法1：回溯法生成唯一排列 #

通过跟踪每个元素的剩余可用数量，递归构造排列，从根源上避免重复：

from collections import Counter

pos = ['QB', 'QB', 'QB',
       'RB', 'RB', 'RB', 'RB', 'RB', 'RB', 'RB', 'RB', 'RB', 'RB', 'RB',
       'WR', 'WR', 'WR', 'WR', 'WR', 'WR', 'WR', 'WR', 'WR', 'WR', 'WR',
       'TE', 'TE', 'TE', 'TE', 'TE']

def unique_permutations(elements, target_length):
    elem_counts = Counter(elements)
    elem_keys = list(elem_counts.keys())
    result = []

    def backtrack(current_list):
        if len(current_list) == target_length:
            result.append(tuple(current_list))
            return
        for key in elem_keys:
            if elem_counts[key] > 0:
                # 选择当前元素
                elem_counts[key] -= 1
                current_list.append(key)
                backtrack(current_list)
                # 回溯
                current_list.pop()
                elem_counts[key] += 1

    backtrack([])
    return result

# 生成目标长度的唯一排列
combos = unique_permutations(pos, 18)

方法2：基于位置组合构造排列 #

如果元素分类明确，可以先确定每种元素的选取数量，再通过组合算法分配位置，避免冗余计算：

import itertools

pos_limits = {'QB': 3, 'RB': 11, 'WR': 11, 'TE': 5}
target_length = 18

def generate_unique_permutations():
    result = []
    # 遍历所有合法的元素数量组合（q+r+w+t=18，且不超过各自上限）
    for q in range(0, min(pos_limits['QB'], target_length) + 1):
        remaining = target_length - q
        for r in range(0, min(pos_limits['RB'], remaining) + 1):
            remaining2 = remaining - r
            for w in range(0, min(pos_limits['WR'], remaining2) + 1):
                t = remaining2 - w
                if 0 <= t <= pos_limits['TE']:
                    # 分配每个元素的位置
                    all_positions = list(range(target_length))
                    # 选QB的位置
                    for q_pos in itertools.combinations(all_positions, q):
                        leftover_pos = [p for p in all_positions if p not in q_pos]
                        # 选RB的位置
                        for r_pos in itertools.combinations(leftover_pos, r):
                            leftover_pos2 = [p for p in leftover_pos if p not in r_pos]
                            # 选WR的位置
                            for w_pos in itertools.combinations(leftover_pos2, w):
                                # 剩余位置填充TE
                                combo = [''] * target_length
                                for p in q_pos:
                                    combo[p] = 'QB'
                                for p in r_pos:
                                    combo[p] = 'RB'
                                for p in w_pos:
                                    combo[p] = 'WR'
                                for p in leftover_pos2:
                                    if p not in w_pos:
                                        combo[p] = 'TE'
                                result.append(tuple(combo))
    return result

combos = generate_unique_permutations()

关键注意事项 #

即使是高效方法，生成18长度的唯一排列数量依然极大（比如选3QB、5RB、7WR、3TE的情况下，排列数约为1.3×10¹⁰），会占用巨量内存和时间。如果你的需求不是必须生成所有排列，建议调整方向：

• 若只需计数，直接用组合数学公式：总排列数 = 18! / (q!×r!×w!×t!)（其中q、r、w、t为各元素选取数量，满足q+r+w+t=18且不超过各自上限）
• 若只需抽样，可通过随机分配位置的方式生成唯一排列，无需遍历全部

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