How to enumerate all valid options for building a course schedule in R

Question

How can I use R to enumerate all possible ways to build a course schedule?

If a student has four compulsory subjects offered at various times, how can I map all possible "paths" the student could take through these subjects without creating a schedule conflict?

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,
  )

The table above shows the different times that the four subjects are being offered. It's easy to see a few different options here, such as:

• class1 at 8,
• class2 at 11,
• class3 at 10, and
• class4 at 9.

But how can I list all conflict-free ways to take these four classes?

I've tried a nested for loop to brute force my way through this... BUT I'd love a more clever way to get to a solution, perhaps through some creative data wrangling, graph methods, or at least a clever for loop?

Once you get to, say 8 different classes--each of which being offered 8 different times throughout a week--we end up with huge numbers (8^8) for a for loop to be running through every possibility.

Answer 1

Here is one way - pivot the data to long format and filter to get time and class pairs, split by class and expand to get all combinations and filter out any rows that have duplicate times.

library(dplyr)
library(tidyr)

class_offerings %>%
  pivot_longer(-time, names_to = "class") %>%
  filter(value == 1) %>%
  select(-value) %>%
  split(~class) %>%
  lapply(`[[`, 1) %>%
  expand.grid() %>% 
  filter(apply(., 1, \(x) !any(duplicated(x))))

  class1 class2 class3 class4
1   8:00  11:00  10:00   9:00
2  12:00  11:00  10:00   9:00
3   8:00  11:00  10:00  12:00