多归属行分组分配问题：求pseudo code、numpy/pandas/SQL实现方案

问题描述 #

现有一张存储唯一物品的表，每行数据的组列标记了该行可归属的1个或多个分组。要求将每行仅分配到一个分组，在每个分组不超过指定大小限制的前提下，最大化所有分组的总已分配行数。由于表中总行数大概率大于所有分组大小限制之和，因此部分行需要被丢弃。

输入输出示例 #

输入
ID   Groups
(4, [s1, s2])
(5, [s1, s2])
(6, [s1])
(15, [s1])
(7, [s2])
(8, [s3])
(10, [s3])
(12, [s3])
(13, [s3])

分组容量限制：s1=3，s2=2，s3=2

期望输出（总分配7行）
s1: 5, 6, 15
s2: 4, 7
s3: 10, 8

反例（总分配仅6行）
s1: 4, 5, 6
s2: 7
s3: 10, 8

核心逻辑 #

该问题属于带容量约束的二分图最大匹配问题，可通过最大流算法得到严格最优解，大数据量下可使用以下贪心近似算法，时间复杂度低且效果接近最优：
优先分配可选分组数量更少的物品，这类物品选择空间小，优先分配可避免后续无组可分配导致的资源浪费。

伪代码实现 #

输入：
1. 物品列表 items：每个元素为 (物品ID, 允许归属的分组列表)
2. 分组容量字典 group_cap：key为分组ID，value为该分组最大可分配数量

初始化：
- group_used: 字典，记录每个分组已分配数量，初始值全为0
- assigned_items: 集合，记录已分配完成的物品ID，初始为空
- result: 字典，记录每个分组的已分配物品列表，初始值全为空列表

步骤：
1. 将items按「允许的分组数量」从小到大排序，可选分组数相同的可自定义排序规则
2. 遍历排序后的每个物品：
   a. 如果该物品已在assigned_items中，跳过
   b. 遍历该物品的允许分组列表，找到第一个满足 group_used[分组] < group_cap[分组] 的分组
   c. 如果找到符合条件的分组：
      i. 将物品ID加入result对应分组的列表
      ii. group_used[对应分组] += 1
      iii. 将物品ID加入assigned_items
   d. 未找到符合条件的分组，直接丢弃该物品
3. 输出result

Pandas实现 #

import pandas as pd

# 模拟输入数据
item_data = pd.DataFrame({
    "id": [4, 5, 6, 15, 7, 8, 10, 12, 13],
    "groups": [["s1","s2"], ["s1","s2"], ["s1"], ["s1"], ["s2"], ["s3"], ["s3"], ["s3"], ["s3"]]
})
group_cap = {"s1":3, "s2":2, "s3":2}

# 拆分多分组为单行
df_explode = item_data.explode("groups", ignore_index=True)
# 统计每个物品的可选分组数
df_explode["option_cnt"] = df_explode.groupby("id")["groups"].transform("count")
# 按可选数升序排序，优先分配选择空间小的物品
df_explode = df_explode.sort_values(["option_cnt", "id"], ascending=[True, True])

# 分配逻辑
used_cnt = {g:0 for g in group_cap}
assigned = set()
output = {g:[] for g in group_cap}

for _, row in df_explode.iterrows():
    item_id = row["id"]
    group = row["groups"]
    if item_id in assigned:
        continue
    if used_cnt[group] < group_cap[group]:
        output[group].append(item_id)
        used_cnt[group] += 1
        assigned.add(item_id)

print(output)
# 输出结果：{'s1': [6, 15, 5], 's2': [7, 4], 's3': [8, 10]}

SQL实现（PostgreSQL） #

假设存在两张输入表：

• item_groups：存储物品可选分组，字段为item_id、group_id
• group_limits：存储分组容量限制，字段为group_id、max_size

WITH item_option_cnt AS (
    -- 统计每个物品的可选分组数，越少优先级越高
    SELECT item_id, COUNT(DISTINCT group_id) AS option_cnt
    FROM item_groups
    GROUP BY item_id
),
ranked_item_groups AS (
    -- 按优先级排序物品
    SELECT 
        ig.item_id,
        ig.group_id,
        -- 同一物品的可选分组按自定义规则排序
        ROW_NUMBER() OVER(PARTITION BY ig.item_id ORDER BY ig.group_id) AS group_priority
    FROM item_groups ig
    JOIN item_option_cnt oc ON ig.item_id = oc.item_id
    ORDER BY oc.option_cnt ASC, ig.item_id ASC
),
group_assignment_candidate AS (
    -- 给每个分组内的候选物品排序，取前N个符合容量限制的
    SELECT 
        rig.item_id,
        rig.group_id,
        ROW_NUMBER() OVER(PARTITION BY rig.group_id ORDER BY rig.group_priority ASC) AS rn
    FROM ranked_item_groups rig
    JOIN group_limits gl ON rig.group_id = gl.group_id
)
-- 去重，保证每个物品仅分配到一个分组
SELECT DISTINCT ON (gac.item_id) gac.group_id, gac.item_id
FROM group_assignment_candidate gac
JOIN group_limits gl ON gac.group_id = gl.group_id
WHERE gac.rn <= gl.max_size
ORDER BY gac.item_id, gac.rn ASC;

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