Python如何枚举a个元素划分为b个大小为c的等大分组的所有组合

实现思路 #

直接递归调用itertools.combinations选组会产生重复结果：分组本身不区分先后顺序，同一划分会因为组的选取顺序不同被重复统计b!次（b为分组总数）。比如a=4、b=2、c=2的场景，直接递归选组会生成6种结果，比正确值多1倍，就是2!的组顺序重复导致的。

最高效的去重逻辑不需要生成全量结果后再判重：每次选组时，固定把当前剩余元素里的第一个元素放到当前正在选的组里，只需要从剩下的元素中选c-1个和它凑成大小为c的组即可，从根源上避免组顺序带来的重复计数，没有额外性能开销。

完整实现代码 #

import itertools
from typing import List, Tuple

def generate_equal_partitions(a: int, b: int, c: int) -> List[List[Tuple]]:
    """
    将1~a的a个元素划分为b个大小为c的无顺序分组，枚举所有合法划分
    参数要求：必须满足 a == b * c，否则抛出参数错误
    """
    if a != b * c:
        raise ValueError("参数不合法，必须满足 总元素数a = 分组数b * 每组大小c")
    
    def _recurse(remaining: List[int]):
        # 递归终止：无剩余元素，返回空划分结构
        if not remaining:
            yield []
            return
        # 固定取剩余元素的第一个，避免组顺序重复
        first_elem = remaining[0]
        rest_elems = remaining[1:]
        # 从剩余元素选c-1个，和固定元素凑成当前组
        for combo in itertools.combinations(rest_elems, c - 1):
            current_group = (first_elem,) + combo
            # 提取选完当前组后剩下的元素
            left_elems = [x for x in rest_elems if x not in combo]
            # 递归生成后续分组
            for follow_groups in _recurse(left_elems):
                yield [current_group] + follow_groups
    
    return list(_recurse(list(range(1, a+1))))

效果验证 #

测试用例1：a=4、b=2、c=2 #

运行代码：

print(generate_equal_partitions(4, 2, 2))

输出和期望结果完全一致：

[[(1, 2), (3, 4)], [(1, 3), (2, 4)], [(1, 4), (2, 3)]]

测试用例2：a=3、b=3、c=1 #

运行代码：

print(generate_equal_partitions(3, 3, 1))

输出符合预期：

[[(1,), (2,), (3,)]]

测试用例3：a=12、b=3、c=4 #

运行后返回结果的长度为5775，和给定的组合数完全匹配，无重复无遗漏。

适配说明 #

• 如果需要分组内为列表而非元组，将current_group的构造逻辑改为列表类型即可
• 如果需要划分0开头的连续整数，将初始传入递归函数的参数改为list(range(a))即可
• 如果需要划分自定义元素列表，直接将初始传入递归函数的参数替换为你的自定义元素列表即可

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