求列表[1,1,1,2,2,2]的20种不重复组合的实现方案

你提到的问题是要生成列表[1,1,1,2,2,2]的所有不重复排列（你说的“组合”其实更准确的是排列，因为元素顺序不同但元素组成相同的情况需要保留，比如[1,1,2,1,2,2]和[1,2,1,2,1,2]是不同的排列），总数刚好是20种，这其实是组合数C(6,3)的结果——从6个位置里选3个放1，剩下的放2，每个位置组合对应唯一的排列，不会有重复。

下面给你两种实用的实现方案，分别适合不同的场景：

方法一：基于位置选择的高效实现 #

这种方法直接利用组合数的特性，跳过所有可能的重复，是最高效的方式，尤其适合元素种类少的情况：

import itertools

def get_unique_permutations(input_list):
    # 统计列表中1的数量（也可以用其他元素，这里以1为例）
    num_ones = input_list.count(1)
    total_elements = len(input_list)
    
    # 生成所有选num_ones个位置的组合，每个组合对应一个唯一排列
    for positions in itertools.combinations(range(total_elements), num_ones):
        permutation = [2] * total_elements
        for pos in positions:
            permutation[pos] = 1
        yield permutation

# 测试代码
original = [1,1,1,2,2,2]
unique_perms = list(get_unique_permutations(original))

print(f"总共生成了{len(unique_perms)}种不重复排列：")
for perm in unique_perms:
    print(perm)

原理说明 #

因为我们的列表只有两种元素，且数量固定（3个1和3个2），所以只需要确定哪些位置放1，剩下的位置自然就是2。这种方式完全不会产生重复，而且直接精准生成20种结果，没有多余的计算。

方法二：回溯法（通用型，适合多重复元素场景） #

如果以后你遇到的列表包含更多种类的重复元素，回溯法去重是更通用的方案：

def backtrack_unique_perms(input_list):
    input_list.sort()  # 先排序，让相同元素相邻，方便去重
    result = []
    used = [False] * len(input_list)
    
    def backtrack(current_path):
        # 当当前路径长度等于原列表长度时，保存结果
        if len(current_path) == len(input_list):
            result.append(current_path.copy())
            return
        
        for i in range(len(input_list)):
            # 跳过已经使用过的元素
            if used[i]:
                continue
            # 跳过重复选择：如果当前元素和前一个相同，且前一个未被使用，说明是同一层的重复选择
            if i > 0 and input_list[i] == input_list[i-1] and not used[i-1]:
                continue
            
            used[i] = True
            current_path.append(input_list[i])
            backtrack(current_path)
            # 回溯：撤销选择
            used[i] = False
            current_path.pop()
    
    backtrack([])
    return result

# 测试代码
original = [1,1,1,2,2,2]
unique_perms = backtrack_unique_perms(original)

print(f"总共生成了{len(unique_perms)}种不重复排列：")
for perm in unique_perms:
    print(perm)

原理说明 #

通过先排序让相同元素相邻，在回溯的每一层中，如果遇到和前一个元素相同且前一个元素未被使用的情况，说明我们正在重复选择同一类元素，这时候跳过该选择，就能避免生成重复的排列。

两种方法都能准确生成你需要的20种不重复排列，你可以根据自己的场景选择使用~

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