基于ID、位置规则和±25%尺寸范围的R数据框最优匹配实现

问题说明 #

现有两个R数据框auto和manual，需基于以下规则完成最优匹配：

1. 基础匹配条件：
   • 两个数据框的ID必须匹配
   • auto_size与manual_size互相处于对方的±25%范围内（即auto_size ≥ 0.75×manual_size 且 manual_size ≥ 0.75×auto_size）
   • 位置匹配规则：
     • right 可匹配 right/middle
     • middle 可匹配 right/middle/left
     • left 可匹配 left/middle
2. 最优匹配逻辑：
   • 每个auto_repeat_tag和manual_repeat_tag仅能匹配一次
   • 优先选择尺寸组合最大的配对（取auto_size和manual_size中的较大值作为排序依据）

示例数据 #

# 加载依赖包
library(dplyr)
library(tibble)

# 示例auto数据框
auto <- tibble(
  ID = c(1,1,1,2,2),
  auto_repeat_tag = c("A1", "A2", "A3", "A4", "A5"),
  auto_size = c(100, 80, 120, 90, 110),
  auto_pos = c("right", "middle", "left", "middle", "right")
)

# 示例manual数据框
manual <- tibble(
  ID = c(1,1,1,2,2),
  manual_repeat_tag = c("M1", "M2", "M3", "M4", "M5"),
  manual_size = c(90, 110, 70, 100, 85),
  manual_pos = c("right", "middle", "left", "middle", "right")
)

实现步骤 #

1. 生成符合基础条件的候选匹配对 #

先筛选出所有满足ID、尺寸和位置规则的配对，并按组合尺寸最大值降序排序，为后续贪心匹配做准备：

candidates <- auto %>%
  inner_join(manual, by = "ID") %>%
  # 筛选尺寸在±25%范围内的配对
  filter(auto_size >= 0.75 * manual_size,
         manual_size >= 0.75 * auto_size) %>%
  # 筛选符合位置规则的配对
  filter(
    (auto_pos == "right" & manual_pos %in% c("right", "middle")) |
    (auto_pos == "middle" & manual_pos %in% c("right", "middle", "left")) |
    (auto_pos == "left" & manual_pos %in% c("left", "middle"))
  ) %>%
  # 计算配对的最大尺寸，用于排序
  mutate(size_max = pmax(auto_size, manual_size)) %>%
  # 按最大尺寸降序排列，优先匹配大尺寸
  arrange(desc(size_max))

2. 执行一对一最优匹配 #

采用贪心算法，依次选取当前未匹配的最大尺寸配对，标记已使用的auto_repeat_tag和manual_repeat_tag，避免重复匹配：

# 初始化匹配标记
matched <- candidates %>%
  mutate(matched = FALSE)

# 初始化结果容器
final_matches <- tibble()

# 循环完成匹配
while(nrow(filter(matched, !matched)) > 0) {
  # 选取当前未匹配的第一个配对（即最大尺寸的候选）
  current_pair <- filter(matched, !matched) %>% slice(1)
  
  # 将当前配对加入结果
  final_matches <- bind_rows(final_matches, current_pair)
  
  # 标记该配对对应的auto和manual标签为已匹配
  matched <- matched %>%
    mutate(matched = if_else(auto_repeat_tag == current_pair$auto_repeat_tag | 
                               manual_repeat_tag == current_pair$manual_repeat_tag,
                             TRUE, matched))
}

# 整理最终结果，去掉辅助列
final_result <- final_matches %>%
  select(-size_max, -matched) %>%
  arrange(ID, auto_repeat_tag)

查看结果 #

运行上述代码后，输出的final_result即为最优匹配结果：

print(final_result)
#> # A tibble: 4 × 7
#>      ID auto_repeat_tag auto_size auto_pos manual_repeat_tag manual_size manual_pos
#>   <dbl> <chr>                <dbl> <chr>    <chr>                    <dbl> <chr>    
#> 1     1 A1                     100 right    M2                        110 middle   
#> 2     1 A3                     120 left     M3                         70 left     
#> 3     2 A4                      90 middle   M5                         85 right    
#> 4     2 A5                     110 right    M4                        100 middle

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