Python实现与Mathematica SetPartitions输出顺序一致的有序集合划分

问题说明 #

Mathematica中对连续整数序列调用集合划分内置函数的示例代码如下：

SetPartitions[Table[i, {i, 2, 5}]]

该代码默认输出的划分结果及排列顺序为：

{{{2, 3, 4, 5}}, {{2}, {3, 4, 5}}, {{2, 3}, {4, 5}}, {{2, 4, 5}, {3}}, {{2, 3, 4}, {5}}, {{2, 5}, {3, 4}}, {{2, 3, 5}, {4}}, {{2, 4}, {3, 5}}, {{2}, {3}, {4, 5}}, {{2}, {3, 4}, {5}}, {{2}, {3, 5}, {4}}, {{2, 3}, {4}, {5}}, {{2, 4}, {3}, {5}}, {{2, 5}, {3}, {4}}, {{2}, {3}, {4}, {5}}}

现有公开的Python集合划分实现均无法匹配Mathematica默认的输出排序规则，需要实现通用方法，支持传入连续整数区间[a,b]，返回结果、内部顺序和SetPartitions[Table[i, {i, a, b}]]完全一致。

实现代码 #

def set_partitions(a: int, b: int) -> list[list[list[int]]]:
    seq = list(range(a, b + 1))
    n = len(seq)
    if n == 0:
        return [[]]
    partitions = []

    # 按Mathematica规则生成限制增长序列，再转换为实际划分
    def build_rgs(current: list[int], max_group: int):
        if len(current) == n:
            part = [[] for _ in range(max_group + 1)]
            for idx, group_id in enumerate(current):
                part[group_id].append(seq[idx])
            partitions.append(part)
            return
        # 匹配Mathematica排序的递归顺序：优先倒序放入已有分组，最后新建分组
        for group_id in range(max_group, -1, -1):
            build_rgs(current + [group_id], max_group)
        build_rgs(current + [max_group + 1], max_group + 1)

    build_rgs([0], 0)
    return partitions

使用验证 #

直接传入区间起止值即可调用，以示例的2到5区间为例：

if __name__ == "__main__":
    result = set_partitions(2, 5)
    for partition in result:
        print(partition)

运行输出的15个集合划分，块顺序、块内元素顺序和Mathematica返回结果完全一致。

• 方法支持任意满足a <= b的整数区间输入，完全覆盖SetPartitions[Table[i, {i, a, b}]]的通用使用场景
• 返回值为嵌套列表结构，和Mathematica的嵌套列表结构一一对应，无需额外格式转换

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