Python从9元素列表中查找符合要求的三元组划分组合集

可用第三方库 #

可以直接使用more-itertools库的set_partitions接口，无需自己实现逻辑：

1. 安装命令：pip install more-itertools
2. 代码示例：

from more_itertools import set_partitions

a = [1,2,3,4,5,6,7,8,9]
# k=3表示划分为3个子集，自动保证每个元素仅出现一次
result = list(set_partitions(a, k=3))
# 过滤得到所有子集大小均为3的划分
a_new = [p for p in result if all(len(subset)==3 for subset in p)]
# 可选：将子集转成有序列表，统一输出格式
a_new = [ [sorted(sub) for sub in p] for p in a_new ]

最终得到的a_new总共有280种合法划分，符合数学计算结果。

原生Python实现思路（无需第三方库） #

直接基于标准库itertools.combinations递归生成即可，逻辑如下：

• 每次从剩余未使用的元素中，用combinations生成所有不重复的三元组（自动满足三元组内部顺序不敏感的约束）
• 选中一个三元组后，从剩余元素中移除这三个元素，继续生成下一个三元组
• 当生成满3个三元组时，将当前划分去重后存入结果集
• 最后对所有划分做全局去重，避免因三元组选择顺序不同导致的重复划分，比如[[1,2,3],[4,5,6],[7,8,9]]和[[4,5,6],[1,2,3],[7,8,9]]属于同一种划分

原生实现代码示例：

import itertools

a = [1,2,3,4,5,6,7,8,9]
result = set()

def generate_partitions(remaining, current_partition):
    if len(current_partition) == 3:
        # 对划分内的三元组排序，保证同一种划分的表示唯一
        sorted_part = tuple(sorted(tuple(sorted(sub)) for sub in current_partition))
        result.add(sorted_part)
        return
    # 固定选第一个元素作为三元组的第一个元素，减少重复递归
    first = remaining[0]
    for pair in itertools.combinations(remaining[1:], 2):
        group = (first,) + pair
        new_remaining = [x for x in remaining if x not in group]
        generate_partitions(new_remaining, current_partition + [group])

generate_partitions(a, [])
# 转成要求的列表格式
a_new = [ [list(sub) for sub in part] for part in result ]

约束满足说明 #

• 同一划分内无重复元素：每次生成三元组都从剩余未使用元素中选取，不会出现元素重复
• 三元组顺序不敏感：使用combinations生成无序三元组，且存入结果前对三元组和划分整体排序，完全消除顺序带来的重复

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