寻求稳健数字列表拆分方法：满足和占比与数量均衡条件

需求 #

将数字列表拆分为两个子集，需同时满足：

• 子集总和占原列表总和的比例落在指定区间（例如45%-55%）
• 两个子集的元素数量差异不超过总数量的5%（即数量大致相等）

现有方案局限 #

当前实现了一种基于正态分布概率的随机分配方法，仅在添加循环控制数量条件后适用于小型列表。该方案需要数百次迭代才能大概率找到符合要求的拆分，缺乏稳健性，需要无需反复试错的可靠方案。

现有实现代码 #

import numpy as np
from scipy.stats import norm

def split_into_normal_distributions(numbers, target_percentage):
    # 计算两个正态分布的均值和标准差
    mean_1 = np.mean(numbers) * target_percentage
    mean_2 = np.mean(numbers) * (1 - target_percentage)
    std = np.std(numbers)

    # 初始化子集
    subset_1 = []
    subset_2 = []

    for num in numbers:
        # 计算当前数字在两个分布中的概率密度
        pdf_1 = norm.pdf(num, loc=mean_1, scale=std)
        pdf_2 = norm.pdf(num, loc=mean_2, scale=std)

        # 计算分配概率比例
        ratio = pdf_1 / (pdf_1 + pdf_2)

        # 根据概率随机分配到子集
        if np.random.rand() < ratio:
            subset_1.append(num)
        else:
            subset_2.append(num)

    return subset_1, subset_2

# 示例数字列表
numbers = [10, 20, 30, 40, 50, 60, 70, 80,10,20,25,20,21,26,65,95,84,65,2,3,6,198,16,651,984,651,35,61,651,16,56,651,651,651,2,32,615,651,984,615,351,651,651,3,5]

# 按目标比例40%/60%拆分
subset_1, subset_2 = split_into_normal_distributions(numbers, 0.4)

print("子集1（目标占比40%）：", subset_1, "实际占比：", sum(subset_1)/sum(numbers), "元素数量：", len(subset_1))
print("子集2（目标占比60%）：", subset_2, "实际占比：", sum(subset_2)/sum(numbers), "元素数量：", len(subset_2))
print("总元素数：", len(numbers))

稳健解决方案 #

1. 整数规划法（精确解） #

将问题建模为整数线性规划，能精确满足所有约束，适合中等规模的列表：

from pulp import LpProblem, LpVariable, LpMinimize, lpSum, value

def split_with_integer_programming(numbers, target_low, target_high):
    total_elements = len(numbers)
    total_sum = sum(numbers)
    # 数量约束：每个子集元素数在总数量的47.5%-52.5%之间（差异≤5%）
    min_subset_size = int(total_elements * 0.475)
    max_subset_size = int(total_elements * 0.525)

    # 创建规划问题
    prob = LpProblem("SubsetSplit", LpMinimize)
    # 定义二进制变量：x[i]=1表示第i个元素分到子集1，0表示分到子集2
    x = [LpVariable(f"x_{i}", cat="Binary") for i in range(total_elements)]

    # 目标函数：最小化子集1总和与目标中间值的偏差
    target_mid_sum = total_sum * (target_low + target_high) / 2
    prob += lpSum([x[i] * numbers[i] for i in range(total_elements)]) - target_mid_sum

    # 总和比例约束
    prob += lpSum([x[i] * numbers[i] for i in range(total_elements)]) >= total_sum * target_low
    prob += lpSum([x[i] * numbers[i] for i in range(total_elements)]) <= total_sum * target_high

    # 元素数量约束
    prob += lpSum(x) >= min_subset_size
    prob += lpSum(x) <= max_subset_size

    # 求解
    prob.solve()

    # 提取结果
    subset_1 = [numbers[i] for i in range(total_elements) if value(x[i]) == 1]
    subset_2 = [numbers[i] for i in range(total_elements) if value(x[i]) == 0]
    return subset_1, subset_2

# 使用示例
subset_1, subset_2 = split_with_integer_programming(numbers, 0.4, 0.6)
print("整数规划结果：")
print(f"子集1：总和占比{sum(subset_1)/sum(numbers):.2%}，元素数{len(subset_1)}")
print(f"子集2：总和占比{sum(subset_2)/sum(numbers):.2%}，元素数{len(subset_2)}")

2. 贪心+局部调整法（高效近似解） #

适合大规模列表，通过贪心分配+局部元素交换快速满足约束：

def split_with_greedy_adjustment(numbers, target_low, target_high):
    sorted_nums = sorted(numbers, reverse=True)
    subset_1, subset_2 = [], []
    total_sum = sum(numbers)
    total_elements = len(numbers)
    min_size = int(total_elements * 0.475)
    max_size = int(total_elements * 0.525)

    # 第一步：交替分配大元素，优先平衡数量
    for num in sorted_nums:
        if len(subset_1) <= len(subset_2):
            subset_1.append(num)
        else:
            subset_2.append(num)

    # 调整数量到约束范围内
    while len(subset_1) < min_size:
        move_num = min(subset_2)
        subset_2.remove(move_num)
        subset_1.append(move_num)
    while len(subset_1) > max_size:
        move_num = min(subset_1)
        subset_1.remove(move_num)
        subset_2.append(move_num)

    # 第二步：调整总和到目标区间
    current_ratio = sum(subset_1) / total_sum
    while not (target_low <= current_ratio <= target_high):
        if current_ratio < target_low:
            # 交换子集2的最大元素和子集1的最小元素，提升子集1总和
            s1_min, s2_max = min(subset_1), max(subset_2)
            if s2_max <= s1_min:
                break  # 无法再调整
            subset_1.remove(s1_min)
            subset_2.remove(s2_max)
            subset_1.append(s2_max)
            subset_2.append(s1_min)
        else:
            # 交换子集1的最大元素和子集2的最小元素，降低子集1总和
            s1_max, s2_min = max(subset_1), min(subset_2)
            if s1_max <= s2_min:
                break
            subset_1.remove(s1_max)
            subset_2.remove(s2_min)
            subset_1.append(s2_min)
            subset_2.append(s1_max)
        current_ratio = sum(subset_1) / total_sum

    return subset_1, subset_2

# 使用示例
subset_1, subset_2 = split_with_greedy_adjustment(numbers, 0.4, 0.6)
print("\n贪心调整结果：")
print(f"子集1：总和占比{sum(subset_1)/sum(numbers):.2%}，元素数{len(subset_1)}")
print(f"子集2：总和占比{sum(subset_2)/sum(numbers):.2%}，元素数{len(subset_2)}")

内容的提问来源于stack exchange，提问作者M. Chris