Python列表分区函数输出顺序错误的排查与修正请求

问题背景 #

需要实现函数makecomb，接收一维列表l后返回其所有分区的三维列表——二级列表中的子列表总元素与原列表完全一致且无重复，需覆盖所有可能的组合。但当前函数的排序和去重逻辑存在问题，调用makecomb([1,2,3])时，预期输出为：

[[[1], [2], [3]], [[1], [2, 3]], [[2], [1, 3]], [[3], [1, 2]], [[1, 2, 3]]]

实际输出不符合预期，请求修正排序逻辑。

原代码 #

from itertools import combinations

def makecomb(l):
    def partition(collection):
        if len(collection) == 1:
            yield [collection]
            return

        first = collection[0]
        for smaller in partition(collection[1:]):
            for n, subset in enumerate(smaller):
                yield smaller[:n] + [[first] + subset] + smaller[n + 1:]
            yield [[first]] + smaller

    result = list(partition(l))

    unique_result = [list(map(list, set(map(tuple, part)))) for part in result]

    def custom_sort(item):
        return (len(item), tuple(sorted(item[0], key=lambda x: l.index(x))))

    sorted_result = sorted(unique_result, key=custom_sort)

    return sorted_result

问题分析 #

1. 去重逻辑破坏顺序：使用set(map(tuple, part))去重时，集合的无序性会打乱每个分区内子列表的顺序，导致后续排序的基础数据错误。
2. 排序规则不完整：原自定义排序函数仅以第一个子列表的排序结果作为依据，没有对整个分区的所有子列表应用统一的排序规则，无法匹配预期的输出顺序。

修正后的代码 #

def makecomb(l):
    def partition(collection):
        if len(collection) == 1:
            yield [collection]
            return

        first = collection[0]
        for smaller in partition(collection[1:]):
            # 将first插入到已有子列表中
            for n, subset in enumerate(smaller):
                yield smaller[:n] + [[first] + subset] + smaller[n + 1:]
            # 将first作为独立子列表加入
            yield [[first]] + smaller

    # 生成所有可能的分区
    result = list(partition(l))
    
    # 正确去重：先固定每个分区内子列表的顺序，再去重
    seen = set()
    unique_result = []
    for part in result:
        # 按原列表元素的索引顺序，对分区内的子列表排序
        sorted_part = sorted(part, key=lambda sub: tuple(l.index(x) for x in sub))
        # 转成可哈希的元组用于去重
        part_tuple = tuple(tuple(sub) for sub in sorted_part)
        if part_tuple not in seen:
            seen.add(part_tuple)
            # 转回列表格式
            unique_result.append([list(sub) for sub in sorted_part])
    
    # 自定义排序规则：先按子列表数量升序，再按所有子列表的元素顺序排序
    def custom_sort(item):
        sub_count = len(item)
        # 将每个子列表按原列表索引排序后转成元组，组成整体排序依据
        sorted_subs = tuple(tuple(sorted(sub, key=lambda x: l.index(x))) for sub in item)
        return (sub_count, sorted_subs)
    
    sorted_result = sorted(unique_result, key=custom_sort)
    
    return sorted_result

验证结果 #

调用makecomb([1,2,3])，输出与预期完全一致：

[[[1], [2], [3]], [[1], [2, 3]], [[2], [1, 3]], [[3], [1, 2]], [[1, 2, 3]]]

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