list、dict和set的综合应用：排课系统（3）
list、dict和set的综合应用：排课系统（3）
上回说到，我们完成了用来测试排课算法的相关数据的添加，这次我们就来实现排课算法，算法相对来说比较复杂，主要用到的数据结构有 list、dict 以及 set，至于这些数据结构如何使用，下面就进行讲解。
概述
考虑到排课的主要任务是给一个班级的一门课程安排教师、教室等资源，解决各种冲突；这个逻辑和操作系统进程获取资源类似，所以排课需要定义两样东西：（1）请求资源的最小单位的集合，（2）各种资源对应的分配表。
知道这些写出排课框架简直就是轻而易举，代码如下：
class CourseScheduling:
def __init__(self):
pass
def schedule_course(self):
print(f'{self} schedule_course')
这里做了一个输出，刷一下存在感，我们下面要去看是否可以正常调用
调用
在实现排课算法之前，我们需要想一下 Django 如何调用这个算法.很明显，我们可以去视图层调用方法，函数视图直接在函数里面调用，类视图在重写的 get_context_data 方法里面调用，我来简单演示一下，首先来编写 course_scheduling_system\views.py，代码如下：
from django.shortcuts import render
from.course_scheduling import CourseScheduling
# Create your views here.
def index(request):
CourseScheduling().schedule_course()
return render(request, 'index.html')
然后去模板文件夹（templates）新建一个名叫 index.html 的文件，文件内容随意。
接下来去配置一下 URL，为了方便，直接在首页调用算法进行测试就好。CourseSchedulingSystem\urls.py 代码如下：
from django.contrib import admin
from django.urls import path
from course_scheduling_system.views import index
urlpatterns = [
path('admin/', admin.site.urls),
path('', index)
]
接下来运行项目，浏览器地址栏输入 http://127.0.0.1:8000 进行访问，访问完成后看一下控制台有没有相应的输出，控制台如图所示。
确实有对应的输出，说明调用算法的路子走对了，接下来我们就尝试实现排课算法。
排课算法的实现
排课算法的实现上面简单的提了一下，需要定义两样东西：（1）请求资源的最小单位的集合，（2）各种资源对应的分配表。现在我们来深入研究这两个东西怎么去定义？先看一下请求资源的最小单位的集合，很明显这是一个集合，集合里面的元素是什么？请求资源的最小单位。如何定义请求资源的最小单位？考虑到请求资源的最小单位是一个班级的一门课程，也就是说这个请求资源的最小单位至少应该有班级和课程这两样东西，同时考虑到这个东西需要装到集合中，所以这个东西必须可哈希，结合这两点，我给出两种比较常见的定义方式。
（1）元组，格式如下：
('班级1', '课程1')
（2）自定义的类，类里面必须要有班级和课程这两个属性，格式就不写了。
当然还有其他的定义方式，比如 namedtuple，这里不再讨论。
接下来就是定义各种资源的分配表，在定义之前我们来想一下有哪几种资源？资源主要有教师和教室两种，为了有效的解决冲突，班级我也算作是一种资源，也需要分配表。那么如何定义资源分配表，这里给出两种方法。
（1）二维数组，星期几是第一个维度，第几节课对应第二个维度（反过来也一样），一开始其中所有元素全部为 0，如果被分配就把对应位置的元素改成 1。
（2）字典，字典的键是一个二元组（第一个元素表示星期几，第二个元素表示第几节课），值只有 0 和 1 两种取值，格式如下所示：
{('星期一', '第一节课'): 0...}
因为每一种资源有许多个，为了便于管理，我们可以把同类资源以及它们的分配表放在一起，放在一起之后构成的数据结构就是一个字典，格式如下：
{'资源1': '分配表1'...}
最后我说一下我使用的格式，其中请求资源的最小单位我使用自定义的类，资源分配表使用字典。当然也可以使用我上面提到的其他的格式，但是需要注意：
千万不要用了和我不一样的格式，然后排课算法抄我的代码！这就好比学图这种数据结构，图的定义是邻接矩阵的存储格式，要实现其深度优先遍历算法，你去网上抄一个邻接表的深度优先遍历算法，这样做是绝对不行的，代码十之八九是运行不了的！
下面进入正题，我们来实现资源的初始化，我们先来看一下教室，因为教室需要按照座位数大小进行升序排序，所以我们需要让上面提到的同类资源的分配表字典按照某个原则进行排序。因为字典是无序的，所以我们不能直接排序，而应该使用 collections 模块中的 OrderedDict，代码如下：
from collections import OrderedDict
from django.db.models import Q
from.models import Classroom, Course, Grade, Teacher
class CourseScheduling:
NUMBER_PER_DAY = 5
WEEKS = ('星期一', '星期二', '星期三', '星期四', '星期五')
def __init__(self):
self.classrooms = OrderedDict(sorted({classroom: {
(week, f'第{i+1}节课'): 0for week in self.WEEKS for i in range(self.NUMBER_PER_DAY)
}for classroom in Classroom.objects.all()}.items(), key=lambda classroom: classroom[0].seat_number))
def schedule_course(self):
print(f'{self} schedule_course')
所有教室的资源分配表定义完成了，下面我们来定义所有教师和班级的资源分配表，这两个差不多，不需要排序，利用普通的字典就够了，代码如下：
def __init__(self):
self.classrooms = OrderedDict(sorted({classroom: {
(week, f'第{i+1}节课'): 0for week in self.WEEKS for i in range(self.NUMBER_PER_DAY)
}for classroom in Classroom.objects.all()}.items(), key=lambda classroom: classroom[0].seat_number))
self.grades = {grade: {(week, f'第{i+1}节课'): 0for week in self.WEEKS for i in range(self.NUMBER_PER_DAY)}
for grade in Grade.objects.all()}
self.teachers = {teacher: {(week, f'第{i+1}节课'): 0for week in self.WEEKS for i in range(self.NUMBER_PER_DAY)}
for teacher in Teacher.objects.all()}
资源分配表定义完成了，接下来是定义请求资源的最小单位的集合，代码如下：
from collections import OrderedDict
from django.db.models import Q
from.models import Classroom, Course, Grade, Teacher
class GradeCourse:
def __init__(self, course, grade):
self.course = course
self.grade = grade
class CourseScheduling:
NUMBER_PER_DAY = 5
WEEKS = ('星期一', '星期二', '星期三', '星期四', '星期五')
def __init__(self):
self.classrooms = OrderedDict(sorted({classroom: {
(week, f'第{i+1}节课'): 0for week in self.WEEKS for i in range(self.NUMBER_PER_DAY)
}for classroom in Classroom.objects.all()}.items(), key=lambda classroom: classroom[0].seat_number))
self.grades = {grade: {(week, f'第{i+1}节课'): 0for week in self.WEEKS for i in range(self.NUMBER_PER_DAY)}
for grade in Grade.objects.all()}
self.teachers = {teacher: {(week, f'第{i+1}节课'): 0for week in self.WEEKS for i in range(self.NUMBER_PER_DAY)}
for teacher in Teacher.objects.all()}
self.grade_courses = {GradeCourse(course, grade)for course in Course.objects.all()
for grade in course.grades.get_queryset()}
def schedule_course(self):
print(f'{self} schedule_course')
目前基本上该有的东西都有了，那么接下来就是去实现排课算法本身，在实现排课之前我们先想一下一个班级的一门课程怎么安排？安排一个班级的一门课程首先要获取该班级的空闲时间、该课程一周有几节、合理的教室。其中空闲时间是一个集合，该课程一周有几节对应着一个大于 0 的整数，合理的教室就是班级的学生人数大于等于教师座位数的教室，也是个集合吗？不是的，因为教室只要选择座位数和班级人数一样的就行，如果没有的话座位数稍微多一点就行，而不至于频繁出现 20 个人的班级拿到 30 个座位的教室，所以需要按照座位数升序排序，先分配座位数少的教室。既然要考虑顺序，所以我们不能使用集合，而应该使用列表。
然后是依次遍历教授这门课程的所有教师，每次遍历从分配表中获取其空闲时间的集合，并且对合理的教室进行遍历，每次遍历的过程中从分配表中获取空闲时间的集合，然后把班级空闲时间集合，教师空闲时间集合，教室空闲时间集合取三者公共部分，构成公共空闲时间。
接下来讨论公共空闲时间的个数和一周课程数量之间的关系。如果公共空闲时间大于等于一周课程数量，就从公共空闲时间中不重复的选取一周课程数量个空闲时间，然后把选中的空闲时间进行遍历，把资源分配表的相应位置的值修改成 1（表示已分配），还要让一周数量自减一；否则我们就直接分配，有多少给多少，没有完事没关系，后面还有空闲的资源。
给出代码之前再次强调：千万不要和我用着不一样的格式，算法的代码实现和我一样，这样做是绝对运行不了的，一定要把上面的逻辑弄懂（不会的话可以加群问我，加群方式见文末）然后根据你的格式用代码实现这个逻辑。我给出我的实现代码，代码如下：
from collections import OrderedDict
from random import sample
from.models import Classroom, Course, Grade, Teacher
class GradeCourse:
def __init__(self, course, grade):
self.course = course
self.grade = grade
class CourseScheduling:
NUMBER_PER_DAY = 5
WEEKS = ('星期一', '星期二', '星期三', '星期四', '星期五')
def __init__(self):
self.classrooms = OrderedDict(sorted({classroom: {
(week, f'第{i+1}节课'): 0for week in self.WEEKS for i in range(self.NUMBER_PER_DAY)
}for classroom in Classroom.objects.all()}.items(), key=lambda classroom: classroom[0].seat_number))
self.grades = {grade: {(week, f'第{i+1}节课'): 0for week in self.WEEKS for i in range(self.NUMBER_PER_DAY)}
for grade in Grade.objects.all()}
self.teachers = {teacher: {(week, f'第{i+1}节课'): 0for week in self.WEEKS for i in range(self.NUMBER_PER_DAY)}
for teacher in Teacher.objects.all()}
self.grade_courses = {GradeCourse(course, grade)for course in Course.objects.all()
for grade in course.grades.get_queryset()}
self.grade_courses_scheduled = set()
def schedule_a_course(self, grade_course):
grade_free_times = {free_time for free_time, busy in self.grades[grade_course.grade].items()if busy == 0}
number_per_week = grade_course.course.number_per_week
valid_classrooms = [classroom for classroom in self.classrooms.keys()if
classroom.seat_number >= grade_course.grade.student_number]
for teacher in grade_course.course.teachers.get_queryset():
teacher_free_times = {free_time for free_time, busy in self.teachers[teacher].items()if busy == 0}
for classroom in valid_classrooms:
classroom_free_times = {free_time for free_time, busy in self.classrooms[classroom].items()if busy == 0}
free_times = grade_free_times & teacher_free_times & classroom_free_times
if len(free_times) >= number_per_week:
free_times_selected = sample(free_times, number_per_week)
for free_time in free_times_selected:
self.classrooms[classroom][free_time] = 1
self.grades[grade_course.grade][free_time] = 1
self.teachers[teacher][free_time] = 1
number_per_week -= 1
elif len(free_times) < number_per_week:
for free_time in free_times:
self.classrooms[classroom][free_time] = 1
self.grades[grade_course.grade][free_time] = 1
self.teachers[teacher][free_time] = 1
number_per_week -= 1
if number_per_week == 0:
break
if number_per_week == 0:
self.grade_courses_scheduled.add(grade_course)
break
def schedule_course(self):
for grade_course in self.grade_courses:
self.schedule_a_course(grade_course)
return False if self.grade_courses-self.grade_courses_scheduled else True
生成总课表
调试算法的过程中并没有出现特别明显的报错，但是是不是真的解决了冲突我们还需要进一步验证，首先生成总课表，格式使用 pandas 的 DataFrame。那么这个 DataFrame 有哪些列？稍微想一下，我们可以得出它有课程、班级、教师、教室、星期几、第几节课这六列，知道这些写出生成总课表的简直太简单了（主要是在已有的代码上做修改），代码如下：
from collections import OrderedDict
from pandas import DataFrame
from random import sample
from.models import Classroom, Course, Grade, Teacher
class GradeCourse:
def __init__(self, course, grade):
self.course = course
self.grade = grade
class CourseScheduling:
NUMBER_PER_DAY = 5
WEEKS = ('星期一', '星期二', '星期三', '星期四', '星期五')
def __init__(self):
self.classrooms = OrderedDict(sorted({classroom: {
(week, f'第{i+1}节课'): 0for week in self.WEEKS for i in range(self.NUMBER_PER_DAY)
}for classroom in Classroom.objects.all()}.items(), key=lambda classroom: classroom[0].seat_number))
self.grades = {grade: {(week, f'第{i+1}节课'): 0for week in self.WEEKS for i in range(self.NUMBER_PER_DAY)}
for grade in Grade.objects.all()}
self.teachers = {teacher: {(week, f'第{i+1}节课'): 0for week in self.WEEKS for i in range(self.NUMBER_PER_DAY)}
for teacher in Teacher.objects.all()}
self.grade_courses = {GradeCourse(course, grade)for course in Course.objects.all()
for grade in course.grades.get_queryset()}
self.grade_courses_scheduled = set()
self.course_table = {'课程': [], '班级': [], '教师': [], '教室': [], '星期几': [], '第几节课': []}
def apply_to_course_table(self, course, grade, teacher, classroom, free_time):
self.classrooms[classroom][free_time] = 1
self.grades[grade][free_time] = 1
self.teachers[teacher][free_time] = 1
self.course_table['课程'].append(str(course))
self.course_table['班级'].append(str(grade))
self.course_table['教师'].append(str(teacher))
self.course_table['教室'].append(str(classroom))
self.course_table['星期几'].append(str(free_time[0]))
self.course_table['第几节课'].append(str(free_time[1]))
def schedule_a_course(self, grade_course):
grade_free_times = {free_time for free_time, busy in self.grades[grade_course.grade].items()if busy == 0}
number_per_week = grade_course.course.number_per_week
valid_classrooms = [classroom for classroom in self.classrooms.keys()if
classroom.seat_number >= grade_course.grade.student_number]
for teacher in grade_course.course.teachers.get_queryset():
teacher_free_times = {free_time for free_time, busy in self.teachers[teacher].items()if busy == 0}
for classroom in valid_classrooms:
classroom_free_times = {free_time for free_time, busy in self.classrooms[classroom].items()if busy == 0}
free_times = grade_free_times & teacher_free_times & classroom_free_times
if len(free_times) >= number_per_week:
free_times_selected = sample(free_times, number_per_week)
for free_time in free_times_selected:
number_per_week -= 1
self.apply_to_course_table(grade_course.course, grade_course.grade, teacher, classroom,
free_time)
elif len(free_times) < number_per_week:
for free_time in free_times:
number_per_week -= 1
self.apply_to_course_table(grade_course.course, grade_course.grade, teacher, classroom,
free_time)
if number_per_week == 0:
break
if number_per_week == 0:
self.grade_courses_scheduled.add(grade_course)
break
def schedule_course(self):
for grade_course in self.grade_courses:
self.schedule_a_course(grade_course)
DataFrame(self.course_table).to_csv('curriculum/results.csv', index=False)
return False if self.grade_courses-self.grade_courses_scheduled else True
生成班级课表
总课表有了，我们只需要在其基础之上生成班级的课表即可（当然也可以生成教师的课表，逻辑差不多），班级课表是一个 Excel 表格，有多少个班级，就有多少个工作表，每个工作表的名称必须包含班级的 id 和名称，每个工作表的格式：第一行是显示星期几（从第二列开始），第一列是显示第几节课（从第二行开始），第一行第一列直接空出来。然后对应的位置填上课程、教师、教室，三样东西在一个单元格，一个单元格有三行（第一行是课程，第二行是教师，第三行是教室）。
生成课表的代码如下所示：
def generate_course_table(self):
row_names = ('',)+self.WEEKS
col_names = ('',)+tuple((f'第{i+1}节课'for i in range(self.NUMBER_PER_DAY)))
style = XFStyle()
style.alignment = Alignment()
style.alignment.wrap = Alignment.WRAP_AT_RIGHT
workbook = Workbook()
self.course_table = DataFrame(self.course_table)
self.course_table.to_csv('curriculum/results.csv', index=False)
for grade in self.grades.keys():
sheet = workbook.add_sheet(str(grade), True)
results = DataFrame(self.course_table[self.course_table['班级'] == str(grade)])
for row in range(len(row_names)):
sheet.write(0, row, row_names[row], style)
for col in range(len(col_names)):
sheet.write(col, 0, col_names[col], style)
for result in results.iterrows():
row = row_names.index(result[1]['星期几'])
col = col_names.index(result[1]['第几节课'])
value = '{}\n{}\n{}'.format(result[1]['课程'], result[1]['教师'], result[1]['教室'])
sheet.write(row, col, value, style)
workbook.save('curriculum/班级课表.xls')
去视图函数调用生成课表的方法，看一下运行结果，如图所示。
我们可以发现课表生成了，下回我们就是尝试在首页显示课表，而不是调用排课方法进行排课。
本文分享自 Python机器学习算法说书人 微信公众号，前往查看
如有侵权，请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体分享计划 ，欢迎热爱写作的你一起参与！