计算课程组合以安排学生

Question

我想为高中生配对 classes。学生有他们需要修读的课程列表：

student_1_requests = [:EEN41, :SDN11T, :HUN11, :PPN41, :AUN21T, :TYN21T, :ZJPHN, :ZLUNCH]

候选人时间表是一个散列，其值是同时提供的一组课程：

candidate_schedule = {
  a_band => [:EEN41, :HGN22, :PPN41],
  b_band => [:SDN11T, :HUN11, :EEN41],
  c_band => [:TYN21T, :SLN11],
  d_band => [:PPN41, :TYN21T],
  l_band => [:ZLUNCH],
  e_band => [:EEN41, :SDN11T, :HUN11, :PPN41],
  f_band => [:AUN21T, :TYN21T, :PPN41],
  g_band => [:ZJPHN, :GAN42]
}

学生每天 period/band 需要 class。因此，为了可行，每个组中的至少一门课程必须出现在 student_requests 中，并且对于一天中的每个组，学生必须能够被安排在他们的不同请求中。

我正在根据候选人时间表测试学生的请求以满足大多数学生的需求。我正在尝试回答：

这 candidate_schedule 是否允许为学生安排所有请求？换句话说，是否有至少一种课程组合可以让他们拥有所有 8 门课程，每个组别有一个不同的课程？

有多少种 combinations/different 方法可以将学生安排在他们要求的每门课程中，以及这些组合是什么，如下所示：

student_schedule_options = {
  :option_1 => {a => :EEN41, b => :HUN11, c => :TYN21T, d => :PPN41, e => :SDN11T, f => :AUN21T, g => :ZJPHN},
  :option_2 => ...
}

如果能够看到满足 8 个请求中的 7 个的情况，并让它报告无法匹配的 band 和 course/s，那就更有趣了, 这将有助于对候选时间表进行更改以改进它。

Answer 1

您可以使用 brute-force 方法执行此操作。

我不确定您的 candidate_schedule 变量是否实际上是一个散列，因为键不是字符串或符号，但您确实只需要一个数组数组。如果是散列，从 candidate_schedule 散列中提取值：

>> schedule = candidate_schedule.values
=> [[:EEN41, :HGN22, :PPN41],
 [:SDN11T, :HUN11, :EEN41],
 [:TYN21T, :SLN11],
 [:PPN41, :TYN21T],
 [:ZLUNCH],
 [:EEN41, :SDN11T, :HUN11, :PPN41],
 [:AUN21T, :TYN21T, :PPN41],
 [:ZJPHN, :GAN42]]

现在，使用 Ruby 的数组方法，创建一组学生时间表的所有可能排列，并且 select 只有所有元素都匹配 class 在同一索引处安排元素：

>> student_schedule_options = student_1_requests.permutation.select { |p| p.each_with_index.all? { |request, i| schedule[i].include?(request) } }
=> [[:EEN41, :SDN11T, :TYN21T, :PPN41, :ZLUNCH, :HUN11, :AUN21T, :ZJPHN],
 [:EEN41, :HUN11, :TYN21T, :PPN41, :ZLUNCH, :SDN11T, :AUN21T, :ZJPHN]]

如果您要处理许多计划，您可能想探索更高效的匹配算法，但这个算法又快又脏。

计算课程组合以安排学生

Calculating combinations of courses for scheduling students

ruby

algorithm

schedule

binary-search