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

标签 ruby algorithm binary-search schedule

我想为高中生匹配类(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),那将更加有趣,这将有助于更改候选人时间表以改进它。

最佳答案

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

我不确定您的 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]]

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

关于ruby - 计算类(class)组合以安排学生,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/42240219/

相关文章:

ruby-on-rails - 如何在 Ruby on Rails 服务器上验证从 Android 发送的 Google token ID?

algorithm - 如何计算顺序重要且集合长度不同的排列?

algorithm - 不成功搜索的二分搜索的平均复杂度

c - 我的二进制搜索实现有什么问题?

ruby - 选择性 Ruby 数组切片

ruby-on-rails - Ruby on Rails 创建和访问 MySQL 变量

ruby-on-rails - 对象未加载

减少信号数据噪声的算法?

algorithm - Ford-Fulkerson最大流算法分析

java - 自定义二分搜索中的 ArrayIndesOutOfBoundsException?