Расчет сочетаний курсов для планирования студентов

Question

Я хочу, чтобы ученики средней школы с классами. Студенты имеют список курсов, которые они должны принять:

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

студент должен иметь класс каждый период/диапазон дня. Таким образом, чтобы быть жизнеспособным, как минимум один из курсов в каждой группе должен появиться в student_requests, и для каждой группы в течение дня студент должен быть в состоянии поместить другой запрос.

Я тестирую запросы студентов на расписание кандидатов, чтобы удовлетворить большинство потребностей студентов. Я пытаюсь ответить:

1. Будет ли это candidate_schedule позволяет студенту быть назначен на все их просьбы? Иными словами, есть ли, по крайней мере, одна комбинация курсов, которая позволила бы им иметь все 8 своих курсов, один курс в каждой группе?

2. В сколько комбинаций/различными способами может студент быть помещен в график кандидата в то же время планируется для каждого курса они обратились с просьбой, и то, что эти комбинации, как это:

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

3. Было бы еще более интригующим, если бы можно было увидеть случаи, когда 7 из 8 запросов могли быть удовлетворены, и сообщить ему группу и курс/с, которые нельзя было бы сопоставить, что позволило бы внести изменения в расписание кандидатов, чтобы улучшить его ,

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

Теперь, используя методы массива рубина, создать набор всех возможных перестановок график студента, и выбрать только те перестановки, в которых все элементы соответствуют другу из расписания класса элементов в том же индексе:

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

Если вы обрабатываете много графиков, вы можете изучить более эффективные алгоритмы сопоставления, но это один быстрый и грязный.