无放回划分超集为指定大小子集：均值逼近超集的算法问询

核心需求 #

将含M个正浮点数元素的超集，无放回划分为N个大小分别为x₀,…,xₙ的子集（满足∑(x₀,…,xₙ)=M），目标是让每个子集的均值尽可能接近超集的均值。需要相关技术建议，包括可检索关键词、高效算法，计划用Python(Numpy)实现。

示例说明 #

示例1：完美分配 #

Superset contains:

- "100" 5 times
- "101" 10 times
- "102" 5 times
mean = 101
Superset = {100, 100, 100, 100, 100, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 102, 102, 102, 102, 102}

Create 3 subsets containing: 2, 4, 14 elements:

A = {100, 102}
B = {100, 102, 100, 102}
C = {100, 100, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 102, 102}

Every subset has a mean of 101.

示例2：最优拟合（无法完美分配） #

Superset contains:

- "100": 5 times
- "103": 10 times
- "104": 5 times
mean = 102.5
Superset = {100, 100, 100, 100, 100, 103, 103, 103, 103, 103, 103, 103, 103, 103, 103, 104, 104, 104, 104, 104}

Create 3 subsets containing: 2, 4, 14 elements:

A = {100, 104}, mean = 102
B = {100, 103, 103, 104}, mean = 102.5
C = {100, 100, 100, 103, 103, 103, 103, 103, 103, 103, 103, 104, 104, 104}, mean = 102.5714 

OR 

A = {100, 104}, mean = 102
B = {100, 103, 104, 104}, mean = 102.75
C = {100, 100, 100, 103, 103, 103, 103, 103, 103, 103, 104, 104, 104, 104}, mean = 102.5

误差函数定义 #

采用各子集与超集均值的偏差之和作为误差指标，目标是最小化该误差。因此示例2中的第一种方案更优。

问题领域与约束 #

希望明确该问题所属的数学/计算机科学领域，以便查阅现有解决方案。同时算法需满足以下约束：

• 日常机器上1秒内完成运行
• 子集数通常为10-25，上限100
• 超集元素数量无上限，但唯一元素数通常为100-1000，边缘情况可达10000

现有初步思路 #

根据超集唯一元素数量和子集数量的差异，针对不同场景设计算法：

1. 轻量级计算场景：枚举所有可能组合，选择最优解
2. 中等计算量场景：从最小子集开始，逐个分配最优元素。虽非绝对公平，但大尺寸子集的均值会自然接近超集均值，整体误差较小
3. 高计算量场景：先通过均匀采样为每个子集预分配50%-75%的元素（使子集均值接近超集均值），再用第二种算法优化剩余元素分配。预分配比例取决于子集数与唯一元素数、超集元素数的比值

尝试过将大规模问题缩小后求解再扩展的思路，但效果不如直接求解原问题；且认为均匀预分配的效果优于该“规模缩减”方法。

寻求建议 #

希望得到以下方面的建议：

• 该问题所属的数学/计算机科学领域关键词，便于检索现有研究
• 符合约束条件的高效算法实现建议（基于Python/Numpy）

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