基于均值优化的超集子集划分策略与实现

from statistics import mean
import pulp

def partition_superset_by_mean(superset_data, set_sizes):
    """
    将超集划分为指定大小的子集，使每个子集的均值尽可能接近超集均值。

    Args:
        superset_data (list): 包含所有元素的超集列表。
        set_sizes (list): 包含每个子集所需元素数量的列表。

    Returns:
        list: 包含划分后子集列表的列表。
    """

    target_sum = sum(superset_data)
    N = len(set_sizes)
    M = len(superset_data)

    # 验证子集大小总和是否等于超集元素总数
    assert sum(set_sizes) == M, "子集大小总和必须等于超集元素总数"

    # 创建 PuLP 问题实例
    set_partitioning_model = pulp.LpProblem("Set_Partitioning_Model", pulp.LpMinimize)

    # 定义决策变量 y_ij
    # covering[s][i] 表示超集中的第 i 个元素是否分配给第 s 个子集
    covering = {}
    for s in range(N):
        vals = []
        for i, v in enumerate(superset_data):
            vals.append(
                pulp.LpVariable(
                    f"assign_set_{s}_element_idx_{i:>02}_val_{v}",
                    lowBound=0,
                    upBound=1,
                    cat=pulp.LpInteger,  # 二进制变量
                )
            )
        covering[s] = vals

    # 定义绝对误差变量 e_s
    abs_sum_errs = []
    for s_i in range(N):
        set_sum_err_abs = pulp.LpVariable(f"set_{s_i}_sum_error_abs")
        abs_sum_errs.append(set_sum_err_abs)

    # OBJECTIVE: 最小化所有子集绝对误差之和
    set_partitioning_model += pulp.lpSum(abs_sum_errs), "Total_Absolute_Error"

    # 添加绝对值线性化约束
    # set_sum_err = (当前子集总和 - 目标子集总和)
    # e_s >= set_sum_err
    # e_s >= -set_sum_err
    superset_mean = target_sum / M
    for s_i, st_vars in covering.items():
        current_set_sum = pulp.lpSum([p * superset_data[i] for i, p in enumerate(st_vars)])
        target_set_sum = set_sizes[s_i] * superset_mean

        # 定义一个中间变量来表示偏差
        set_sum_deviation = pulp.LpVariable(f"set_{s_i}_sum_deviation")
        set_partitioning_model += set_sum_deviation == current_set_sum - target_set_sum, \
                                  f"Deviation_Constraint_Set_{s_i}"

        # 绝对值约束
        set_partitioning_model += abs_sum_errs[s_i] >= set_sum_deviation, \
                                  f"Abs_Error_Positive_Set_{s_i}"
        set_partitioning_model += abs_sum_errs[s_i] >= -set_sum_deviation, \
                                  f"Abs_Error_Negative_Set_{s_i}"

    # 约束1: 子集大小是预设的
    for n, st_vars in zip(set_sizes, covering.values()):
        set_partitioning_model += pulp.lpSum(st_vars) == n, \
                                  f"Set_Size_Constraint_{n}"

    # 约束2: 每个超集元素只能被使用一次
    # zip(*covering.values()) 将所有子集的变量列表转置，以便按元素索引迭代
    for element_idx, element_assignment_vars in enumerate(zip(*covering.values())):
        set_partitioning_model += (
            pulp.lpSum(element_assignment_vars) == 1,
            f"Element_{element_idx}_Used_Once",
        )

    # 求解模型
    set_partitioning_model.solve()

    # 提取结果
    if pulp.LpStatus[set_partitioning_model.status] == 'Optimal':
        result_subsets = []
        print(f"超集均值: {superset_mean}")
        for k, v in covering.items():
            subset_elements = [superset_data[idx] for idx, var in enumerate(v) if var.value() == 1]
            result_subsets.append(subset_elements)
            print(f"子集 {k} ({len(subset_elements)}个元素): {subset_elements}, 均值 = {mean(subset_elements)}")
        return result_subsets
    else:
        print(f"未能找到最优解。状态: {pulp.LpStatus[set_partitioning_model.status]}")
        return None

# 示例 1: 完美分配
print("--- 示例 1: 完美分配 ---")
superset_ex1 = [100]*5 + [101]*10 + [102]*5
set_sizes_ex1 = [2, 4, 14]
partition_superset_by_mean(superset_ex1, set_sizes_ex1)

# 示例 2: 最佳拟合 (完美分配不可能)
print("\n--- 示例 2: 最佳拟合 ---")
superset_ex2 = [100]*5 + [103]*10 + [104]*5
set_sizes_ex2 = [2, 4, 14]
partition_superset_by_mean(superset_ex2, set_sizes_ex2)

--- 示例 1: 完美分配 ---
超集均值: 101.0
子集 0 (2个元素): [101, 101], 均值 = 101
子集 1 (4个元素): [100, 100, 102, 102], 均值 = 101
子集 2 (14个元素): [100, 100, 100, 101, 101, 101, 101, 101, 101, 101, 101, 102, 102, 102], 均值 = 101

--- 示例 2: 最佳拟合 ---
超集均值: 102.5
子集 0 (2个元素): [103, 103], 均值 = 103
子集 1 (4个元素): [100, 100, 104, 104], 均值 = 102
子集 2 (14个元素): [100, 100, 100, 103, 103, 103, 103, 103, 103, 103, 103, 104, 104, 104], 均值 = 102.57142857142857