如何使用R枚举无冲突必修课程表的所有可行方案？

问题背景 #

给定四门必修课程的时段开设数据，需找出所有无时间冲突的选课组合（即每门课选一个时段，且所有时段不重复）。需避免嵌套循环这类暴力枚举方法的低效问题，尤其当课程/时段数量增加时（如8门课对应8个时段，暴力枚举的计算量为8^8，难以承受）。

给定的课程开设数据：

class_offerings <- tibble::tribble(
  ~time,   ~class1,    ~class2,    ~class3,    ~class4,
   "8:00",   1,          0,          0,          0,
   "9:00",   0,          0,          0,          1,
   "10:00",  0,          0,          1,          1,
   "11:00",  0,          1,          0,          1,
   "12:00",  1,          0,          0,          1,
  )

方法一：组合生成+过滤（适合小规模场景） #

先提取每门课的可选时段，再生成所有可能组合，最后过滤出时段无重复的有效方案。

代码实现 #

library(tibble)
library(dplyr)
library(purrr)

# 提取每门课的可选时段列表
class_options <- class_offerings %>%
  select(-time) %>%
  map(~ class_offerings$time[.x == 1])

# 生成所有可能的选课组合，并过滤无冲突方案
valid_schedules <- cross(class_options, .name_repair = "minimal") %>%
  map_dfr(as_tibble) %>%
  rowwise() %>%
  filter(n_distinct(c_across(everything())) == ncol(.)) %>%
  ungroup()

# 查看结果
valid_schedules

方法二：二分图完美匹配（高效适配大规模场景） #

将问题转化为二分图完美匹配问题：左侧节点为课程，右侧节点为时段，课程与可选时段之间连边。我们需要找到所有匹配方式，使得每门课匹配唯一时段，且每个时段仅被一门课占用。这种方法的时间复杂度远低于暴力枚举，适合课程/时段数量较多的场景。

代码实现 #

library(igraph)
library(tibble)
library(dplyr)
library(purrr)

# 构建二分图
# 定义节点：课程（class1-class4） + 时段（8:00-12:00）
nodes <- c(colnames(class_offerings)[-1], class_offerings$time)
# 定义边：课程到其可选时段的连接
edges <- class_offerings %>%
  pivot_longer(-time, names_to = "class", values_to = "offered") %>%
  filter(offered == 1) %>%
  select(class, time) %>%
  as.matrix()

# 创建二分图对象
g <- graph_from_edgelist(edges, directed = FALSE)
V(g)$type <- c(rep(TRUE, 4), rep(FALSE, 5)) # 标记课程节点（TRUE）和时段节点（FALSE）

# 找出所有完美匹配
all_matches <- all_simple_matching(g, type = "all")

# 将匹配结果转换为选课表格式
valid_schedules_graph <- map_dfr(all_matches, function(match) {
  match_df <- as.data.frame(match) %>%
    rename(class = from, time = to) %>%
    filter(class %in% colnames(class_offerings)[-1]) %>%
    arrange(class)
  tibble(
    class1 = match_df$time[match_df$class == "class1"],
    class2 = match_df$time[match_df$class == "class2"],
    class3 = match_df$time[match_df$class == "class3"],
    class4 = match_df$time[match_df$class == "class4"]
  )
})

# 查看结果
valid_schedules_graph

方法对比 #

• 组合生成+过滤：代码简洁直观，适合课程数较少（如4门）的场景，但本质仍是枚举所有可能，课程数增加时计算量会快速上升。
• 二分图匹配：基于图论算法，时间复杂度为多项式级（远低于暴力枚举的指数级），当课程/时段数量增加到8门及以上时，优势极为明显。

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