R语言分组约束下生成物品全组合 支持自定义取数与新组数量

问题描述 #

本问题融合了两类组合生成场景的需求，核心是基于给定原始分组，生成满足约束的所有新分组，约束规则如下：

• 每个新组必须包含来自每个原始组的等量物品
• 所有物品不可重复使用
• 新组内物品顺序不影响结果，同元素不同排列仅保留1种
• 支持自定义两个核心参数：每个新组从单个原始组抽取的物品数、新组总数量
• 不要求各原始组物品数量一致，也不要求原始组数量和新组数量相等

测试用原始分组数据：

original_groups <- list(group_1 = as.character(1:6), group_2 = as.character(7:12), group_3 = as.character(13:20))

场景示例1：每个新组从各原始组抽1个物品，共生成3个新组 #

Number_of_Items_From_Each_Original_Group_to_End_up_in_Each_New_Group <- 1
Number_of_New_Groups <- 3

# 合法结果示例1
new_groups <- list(group_1 = as.character(c(1, 7, 13)), group_2 = as.character(c(2, 8, 14)), group_3 = as.character(c(3, 9, 15)))

# 合法结果示例2
new_groups <- list(group_1 = as.character(c(1, 7, 13)), group_2 = as.character(c(2, 8, 14)), group_3 = as.character(c(3, 9, 16)))

# 合法结果示例3
new_groups <- list(group_1 = as.character(c(1, 8, 13)), group_2 = as.character(c(2, 7, 14)), group_3 = as.character(c(3, 9, 15)))

场景示例2：每个新组从各原始组抽2个物品，共生成3个新组 #

Number_of_Items_From_Each_Original_Group_to_End_up_in_Each_New_Group <- 2
Number_of_New_Groups <- 3

# 合法结果示例1
new_groups <- list(group_1 = as.character(c(1, 2, 7, 8, 13, 14)), group_2 = as.character(c(3, 4, 9, 10, 15, 16)), group_3 = as.character(c(5, 6, 11, 12, 17, 18)))

# 合法结果示例2
new_groups <- list(group_1 = as.character(c(1, 2, 7, 8, 13, 14)), group_2 = as.character(c(3, 4, 9, 10, 15, 16)), group_3 = as.character(c(5, 6, 11, 12, 17, 19)))

# 合法结果示例3
new_groups <- list(group_1 = as.character(c(1, 3, 7, 8, 13, 14)), group_2 = as.character(c(2, 4, 9, 10, 15, 16)), group_3 = as.character(c(5, 6, 11, 12, 17, 18)))

可行性校验规则：对任意原始组，其总物品数必须 ≥ 单组抽取数 * 新组总数，否则无法生成合法分组。例如每个原始组至少有9个物品时，可支持「单组抽3个共3个新组」或「单组抽2个共4个新组」的配置。

以下提供纯base R的实现方案，可直接作为子函数嵌入更大的业务逻辑中。

实现方案 #

核心逻辑分三步：

1. 先做参数合法性校验，提前拦截不可能生成结果的配置
2. 对每个原始组，生成所有将物品划分为指定大小子集的划分方案（自动去重，忽略组内顺序、子集顺序）
3. 对各原始组的划分方案做笛卡尔积，拼接得到所有合法的新分组结果

完整代码：

generate_all_new_groups <- function(original_groups, items_per_group_per_original, n_new_groups) {
  # 参数合法性校验
  group_sizes <- lengths(original_groups)
  required_size <- items_per_group_per_original * n_new_groups
  if (any(group_sizes < required_size)) {
    stop("存在原始组物品数量不足，无法满足当前配置要求")
  }
  
  # 辅助函数：生成单个向量所有划分为k个大小为m的子集的方案（忽略子集顺序、子集内元素顺序）
  generate_partitions <- function(x, m, k) {
    n <- length(x)
    # 当原始组元素总数大于需要抽取的总数时，先生成所有选m*k个元素的组合，再对选中元素做划分
    if (m*k < n) {
      combos <- combn(x, m*k, simplify = FALSE)
      res <- list()
      for (combo in combos) {
        parts <- generate_partitions(combo, m, k)
        res <- c(res, parts)
      }
      return(res)
    }
    # 递归终止条件：只剩1个子集需要生成
    if (k == 1) {
      return(list(list(sort(x))))
    }
    # 固定第一个元素生成组合，避免重复划分
    first_elem <- x[1]
    rest_elems <- x[-1]
    first_group_combos <- combn(rest_elems, m-1, simplify = FALSE)
    partitions <- list()
    for (fg in first_group_combos) {
      first_subset <- sort(c(first_elem, fg))
      remaining <- setdiff(rest_elems, fg)
      sub_parts <- generate_partitions(remaining, m, k-1)
      for (sp in sub_parts) {
        partitions <- c(partitions, list(c(list(first_subset), sp)))
      }
    }
    return(partitions)
  }
  
  # 为每个原始组生成所有合法划分
  group_partitions <- lapply(original_groups, function(g) {
    generate_partitions(g, items_per_group_per_original, n_new_groups)
  })
  
  # 辅助函数：两个划分方案列表做笛卡尔积拼接
  cross_join <- function(a, b) {
    res <- list()
    for (ai in seq_along(a)) {
      for (bi in seq_along(b)) {
        combined <- mapply(c, a[[ai]], b[[bi]], SIMPLIFY = FALSE)
        combined <- lapply(combined, sort)
        names(combined) <- paste0("group_", seq_along(combined))
        res <- c(res, list(combined))
      }
    }
    return(res)
  }
  
  # 迭代拼接所有原始组的划分结果
  final_result <- group_partitions[[1]]
  for (i in 2:length(group_partitions)) {
    final_result <- cross_join(final_result, group_partitions[[i]])
  }
  
  # 全局去重，完全相同的分组仅保留一个
  final_result <- unique(final_result)
  return(final_result)
}

用法示例 #

# 测试场景1：每个新组从各原始组抽1个，共3个新组
res1 <- generate_all_new_groups(original_groups, 1, 3)
# 查看前3个合法结果
head(res1, 3)

# 测试场景2：每个新组从各原始组抽2个，共3个新组
res2 <- generate_all_new_groups(original_groups, 2, 3)
# 查看前3个合法结果
head(res2, 3)

该实现无第三方依赖，自动处理顺序去重、跨组组合、不等长原始组适配逻辑，支持新组数量与原始组数量不一致的配置。

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