基于指定箱容量的分类变量分箱：R语言多可选箱分配问题

需求 #

现有两组数据：

1. 人员姓名与对应的可选分箱列表（每人可选择多个分箱，但最终仅能分配至一个）
2. 各分箱的容量上限
   需要实现高效分配逻辑，满足：

• 所有人员均分配至其可选分箱之一
• 每个分箱的人数不超过指定容量
  此前尝试按分箱可选人数排序迭代分配，但因分箱重叠导致错误移除已分配对象，现寻求可行方案。

示例数据 #

人员可选分箱数据 #

name <- c("James", "Terry", "Fred", "Scottie", "Clint", "Gary", "Kevin", "Harrison", "Patrick")
available_bins <- c("A/B", "A/B", "B", "C/D", "E", "A/D", "A/D", "D/C", "D/C")
init <- data.frame(name, available_bins)
init
#      name available_bins
#1    James            A/B
#2    Terry            A/B
#3     Fred              B
#4  Scottie            C/D
#5    Clint              E
#6     Gary            A/D
#7    Kevin            A/D
#8 Harrison            D/C
#9  Patrick            D/C

分箱容量参数 #

bin_name <- c("A","B","C","D","E")
bin_size <- c(2,2,2,2,1)
binning_parameters <- data.frame(bin_name, bin_size)
binning_parameters
#  bin_name bin_size
#1        A        2
#2        B        2
#3        C        2
#4        D        2
#5        E        1

预期分配结果 #

final_bin <- c("A", "B", "B", "C", "E", "A", "D", "C", "D")
final_bin <- data.frame(name, final_bin)
final_bin
#      name final_bin
#1    James         A
#2    Terry         B
#3     Fred         B
#4  Scottie         C
#5    Clint         E
#6     Gary         A
#7    Kevin         D
#8 Harrison         C
#9  Patrick         D

可行实现方案 #

核心思路 #

优先处理可选分箱数量最少的人员（比如只能选E的Clint），避免后续因分箱容量耗尽导致这类人员无法分配；对每个人员，仅从还有剩余容量的可选分箱中选择，实时更新分箱剩余容量。

R代码实现 #

library(dplyr)
library(tidyr)

# 预处理：拆分可选分箱，按可选数量排序
init_processed <- init %>%
  mutate(available_bins = strsplit(as.character(available_bins), "/")) %>%
  rowwise() %>%
  mutate(num_options = length(available_bins)) %>%
  ungroup() %>%
  arrange(num_options)

# 初始化分箱剩余容量（用分箱名作为索引）
bin_capacity <- setNames(binning_parameters$bin_size, binning_parameters$bin_name)

# 初始化分配结果向量
assignments <- character(nrow(init_processed))

# 迭代分配
for (i in seq_len(nrow(init_processed))) {
  current_options <- init_processed$available_bins[[i]]
  # 筛选当前还有剩余容量的可选分箱
  valid_bins <- current_options[bin_capacity[current_options] > 0]
  # 选择剩余容量最大的分箱（平衡分箱使用率）
  selected_bin <- names(which.max(bin_capacity[valid_bins]))
  
  assignments[i] <- selected_bin
  bin_capacity[selected_bin] <- bin_capacity[selected_bin] - 1
}

# 整理成最终结果，恢复原始姓名顺序
final_result <- init_processed %>%
  select(name) %>%
  mutate(final_bin = assignments) %>%
  arrange(match(name, init$name))

print(final_result)

代码说明 #

• 先按可选分箱数量排序，确保无选择余地的人员优先分配，从根源避免分配冲突
• 每次仅筛选有剩余容量的分箱，严格遵守容量限制
• 选择剩余容量最大的分箱，可平衡各分箱的人员分布，减少后续分配压力
• 最后恢复原始姓名顺序，与输入格式保持一致

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