ruby - 计算类(class)组合以安排学生

Question

我想为高中生匹配类(class)。学生有一份他们需要修读的类(class) list :

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

候选时间表是一个散列，其值是同时提供的一系列类(class):

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]
}

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

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

1. 此 candidate_schedule 是否允许为学生安排他们的所有请求？换句话说，是否存在至少一种类(class)组合，可以让他们拥有所有 8 门类(class)，每个组别有一门不同的类(class)？

2. 在安排学生申请的每门类(class)时，可以将学生以多少种组合/不同方式放入候选时间表，以及这些组合是什么，如下所示:

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

3. 如果有可能看到满足 8 个请求中的 7 个的情况，并让它报告无法匹配的波段和类(class)，那将更加有趣，这将有助于更改候选人时间表以改进它。

Answer 1

您可以使用蛮力方法来做到这一点。

我不确定您的 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 的数组方法，创建一组学生时间表的所有可能排列，并仅选择所有元素都与同一索引处的类(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]]

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