R语言实现带分组变量的指定数量元素全组合枚举

需求规则 #

给定多个原始分组的元素集合，需要枚举所有满足如下规则的新分组划分方案：

• 共划分出固定数量的新分组
• 每个新分组从每一个原始分组中抽取固定数量的元素
• 所有元素不重复使用，每个元素仅能出现在一个新分组中
• 最终输出为list类型对象，每个子元素代表一套完整划分方案，每套方案包含所有新分组

测试输入与示例输出 #

输入数据 #

list1 <- list(
  Group_1 = c("1", "2", "3", "4", "5", "6"), 
  Group_2 = c("13", "14", "15", "16", "17", "18"), 
  Group_3 = c("19", "20", "21", "22", "23", "24", "25")
)
# 每个新分组从单个原始分组抽取的元素个数
items_per_new_group <- 2
# 新分组总数量
new_group_num <- 3

合法输出示例 #

# 方案1
list(
  New_Group_1 = c("1", "2", "13", "14", "19", "20"), 
  New_Group_2 = c("3", "4", "15", "16", "21", "22"), 
  New_Group_3 = c("5", "6", "17", "18", "23", "24")
)

# 方案2
list(
  New_Group_1 = c("3", "4", "13", "14", "19", "20"), 
  New_Group_2 = c("5", "6", "15", "16", "21", "22"), 
  New_Group_3 = c("1", "2", "17", "18", "23", "24")
)

实现代码 #

核心思路是先对每个原始分组单独生成所有符合数量要求的拆分方式，再通过笛卡尔积拼接跨组的所有组合，最后去重得到完整结果。

# 首次运行先安装依赖
# install.packages(c("gtools", "purrr"))
library(gtools)
library(purrr)

enumerate_partitions <- function(original_groups, pick_count, new_group_count) {
  # 单组拆分逻辑：把一个原始向量拆成n_group组，每组pick_count个元素
  split_one_group <- function(x, k, n_g) {
    pick_total <- min(k * n_g, length(x))
    # 生成所有不重复选取的排列
    all_perms <- permutations(length(x), pick_total, x)
    split_list <- list()
    for (row_idx in 1:nrow(all_perms)) {
      current_perm <- all_perms[row_idx, ]
      # 按每k个元素切分为一个新分组
      splits <- split(current_perm, ceiling(seq_along(current_perm)/k))
      names(splits) <- paste0("New_Group_", 1:n_g)
      # 组内排序消除组内顺序导致的重复
      splits <- map(splits, sort)
      split_list[[row_idx]] <- splits
    }
    # 消除重复拆分结果
    unique(split_list)
  }

  # 为每个原始分组生成所有拆分可能
  all_splits_by_original_group <- map(
    original_groups, 
    ~split_one_group(.x, pick_count, new_group_count)
  )

  # 跨原始分组做笛卡尔积，拼接得到完整划分方案
  all_combos <- cross(all_splits_by_original_group)
  final_plans <- map(all_combos, function(combo) {
    map(1:new_group_count, function(g_id) {
      g_name <- paste0("New_Group_", g_id)
      # 把同一新分组下来自不同原始组的元素拼起来
      reduce(map(combo, ~.x[[g_name]]), c)
    }) |> setNames(paste0("New_Group_", 1:new_group_count))
  })

  # 全局去重
  unique(final_plans)
}

# 执行生成所有合法方案
all_results <- enumerate_partitions(list1, items_per_new_group, new_group_num)

使用说明 #

• 示例中Group_3共有7个元素，按规则3个新分组每个拿2个总共只需要6个元素，代码默认会选取6个元素完成分配，如果需要把剩余元素归入指定分组，直接修改拆分逻辑即可
• 如果不需要区分新分组的顺序（比如新分组1和新分组2整体交换算同一种方案），可以在最终结果中对每个方案的分组做排序后再去重
• 当原始分组元素较多时，组合数会爆炸式增长，运行前注意评估数据量避免内存不足

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