为大学制定最优时间表的程序的天真实现

Question

下学期的大学注册很快，所以我决定为一个计划做一个天真的实施(蛮力)，根据我需要参加的工作天数来制定一个最佳的时间表。尽管这个问题是NP难的，但对于我的问题的输入大小来说没有问题(最多6-7门课程)。

关于我们的课程体系，以下是一些需要考虑的问题：

• 每门课程可分为2至3组。
• 学生可以从任何不同的组注册任何课程，但是你必须注册整个课程(也就是说，该课程的部分和实验室必须与讲座来自同一组)。
• 一天分为12个阶段，课程的任何部分(讲座、部分或实验室)都可以是1至3个周期。

首先，这里是CollegeSchedule.py，在这里我有一些类声明

from collections import defaultdict

workdays = ('Saturday', 'Sunday', 'Monday', 'Tuesday', 'Wedensday', 'Thrusday')


class Course():

    """
    This class contains infomation about a college course such as course
    name and in which group it occurs in.
    Each course consists of a lecture and a section at least, some courses
    has extra slot for a lab.
    """

    def __init__(self, name):

        self.name = name
        self.occurances = defaultdict(list)

    def add_slot(self, group, day, periods, type_):
        S = Slot(self, group, day, periods, type_)
        self.occurances[group].append(S)

    def get_group_slots(self, group):
        if group in self.occurances:
            return self.occurances[group]
        # In the rare case where a course is only present in 2 groups only
        return None

    def __str__(self):

        result = ""
        for group, slots in self.occurances.items():
            result += "Group " + str(group) + ":\n"
            for slot in slots:
                result += slot.get_type() + "\n"
                result += "Day: " + \
                    str(slot.day) + " Group: " + str(slot.group) + \
                    " Periods: " + str(slot.periods) + "\n"

        return result


class Slot():

    """
    This class represents a slot in a timetable (part of a course), including the
    type of that part (i.e. lecture, section or lab) along with
    the periods in which that part takes place (We've 12 periods per day, each slot
    can be between 1 to 3 periods),
    Day in which that part occurs,
    group number,
    and course name.
    """

    def __init__(self, course, group, day, periods, type_):
        self.course = course.name
        self.group = group
        self.day = day
        self.periods = periods
        self.type = type_

    def get_type(self):
        return self.type

    def __str__(self):
        result = "Course: " + self.course + " Group " + \
            str(self.group) + " " + str(self.type) + \
            " Periods " + str(self.periods)
        return result

    def __repr__(self):
        return self.__str__()


class Timetable:
    """
    A very simple Timetable representation, Has a dictionary with a
    key being the day number and the value is a list of slots
    that are part of the Timetable.
    """

    def __init__(self):
        self.work_days = defaultdict(list)

    def add_course(self, course_slots):
        """
        Tries to add a whole course (Lecture, section and lab) into the timetable.
        Returns boolean indicating if adding was successful.
        """

        if not course_slots:
            return False

        for slot in course_slots:
            can_add = self.check_slot(slot)
            if not can_add:
                return False
            self.work_days[slot.day].append(slot)

        return True

    def check_slot(self, slot):
        """
        Checks if a slot can be added into the Timetable
        by checking if the slot periods intersect with any other slot
        in the same day.
        """
        day = slot.day

        if not day in self.work_days:
            return True

        for t_slot in self.work_days[day]:
            t_time = t_slot.periods
            time = slot.periods
            new_time = (max(t_time[0], time[0]), min(t_time[1], time[1]))

            if new_time[0] <= new_time[1]:
                return False

        return True

    def print_timetable(self):
        """
        Print the timetable in a sorted way.
        First sorted by days, and inside each day sorted by periods.
        """
        days_list = sorted(self.work_days)
        for day in days_list:
            print(workdays[day])
            self.work_days[day].sort(key=lambda x: x.periods[0])
            print(*self.work_days[day], sep="\n")


    def total_days(self):
        return len(self.work_days)

下面是generate_best_timetables方法，它实际上生成时间表

def generate_best_timetables(courses, MAX_GROUP_NUM = 3):
    """
    Generating every possible solution to the problem, Here I am Generating
    3**N possible tuples Where 3 is the maximum number of groups and N is the number of
    courses to consider.
    Each element value in the tuple correspond to a group number - 1 (0, 1, 2), and the i-th element
    in the tuple correspond to the i-th course in the list of courses.
    i.e. for i-th element in the tuple, we try to add the tuple[i]+1 group of the i-th
    course to the timetable.
    """

    total_tt = []
    best_tt = None
    COURSES_NUM = len(courses)

    for p in product(range(MAX_GROUP_NUM), repeat=COURSES_NUM):
        tt = Timetable()
        valid = True

        for i, val in enumerate(p):
            course_slots = courses[i].get_group_slots(int(val) + 1)
            valid = tt.add_course(course_slots)
            if not valid:
                break

        if valid:
            # Store all the timetables with minimum number of work days
            if not best_tt or tt.total_days() < best_tt.total_days():
                best_tt = tt
                total_tt = [best_tt]
            elif tt.total_days() == best_tt.total_days():
                total_tt.append(tt)

    return total_tt

以及示例数据和主要内容：

# Algorithms
algo = Course("Algorithms")
algo.add_slot(1, 0, (1, 2), "Lecture")
algo.add_slot(1, 0, (3, 4), "Section")
algo.add_slot(1, 1, (3, 4), "Lab")

algo.add_slot(2, 0, (1, 2), "Lecture")
algo.add_slot(2, 2, (1, 2), "Section")
algo.add_slot(2, 3, (1, 2), "Lab")

# OS
os = Course("Operating Systems")
os.add_slot(1, 0, (5, 6), "Lecture")
os.add_slot(1, 0, (7, 8), "Section")
os.add_slot(1, 1, (5, 6), "Lab")

os.add_slot(2, 0, (1, 2), "Lecture")
os.add_slot(2, 4, (7, 8), "Section")
os.add_slot(2, 5, (5, 6), "Lab")

def main():
    courses = [os, algo]
    total_tt = generate_best_timetables(courses)

    for tt in total_tt:
        tt.print_timetable()
        print("Working days: ", tt.total_days())
        print("================================")

关于我的程序我能改进什么？

我知道我在命名变量/类/模块方面有问题，我现在的类结构不是最好的，我用产品在generate_best_timetables中生成下一个可能的时间表的方式有点奇怪，而且性能与问题的大小无关，所以我现在没有真正考虑它。

对于现在的测试，我将手动添加代码中的课程，但我将从文件中填充课程列表(可能是csv文件？)或者数据库。

如果您对我的代码有任何评论，我将不胜感激。

Answer 1

备注：

• workdays元组的良好使用
• 充分利用defaultdict
• 像样的文件。奇怪的包装。应该遵循某种标准。
• 充分利用itertools.product

一些次要的挑剔：

• PEP 8！(行长，格式字符串的"，所有其他字符串的'，等等)
• 我们喜欢class Course:而不是class Course():
• 在以:结尾的行之后，不应该有空行。
• 您应该在工作日使用enum (这将提高以后的可读性--我不知道课程初始化中的这些数字意味着什么)：

class Workday(Enum):
    Saturday = 0
    Sunday = 1
    Monday = 2
    Tuesday = 3
    Wednesday = 4
    Thursday = 5
    # NOTE: Friday missing?

• 在get_group_slots中，in检查不是非常Pythonic的。Python订阅了“尝试”，如果它发生的话，就处理失败。也就是说，在dict中索引一个不存在的键将生成一个KeyError。因此，代码应该如下所示：

def get_group_slots(self, group):
    try:
        return self.occurances[group]
    except KeyError:
        return None

• 您的__str__看起来非常java-y。我们更喜欢通过使用格式字符串(或者f-字符串，如果您使用Python3.6，我将在本例中使用)和string.join (我要补充一点，您在Slot上定义了一个__str__，但不使用它)来构建字符串：

def __str__(self):
    # This is still a bit unwieldy, but it conveys your intent a bit better 
    def str_slot(slot):
        return f'{slot.get_type()}\nDay: {slot.day} Group: {slot.group} ' \
               f'Periods: {slot.periods}'

    return '\n'.join("Group {}:\n{}".format(group, '\n'.join(map(str_slot, slots)))
                     for group, slots in self.occurances.items())

• 在Slot上，将__repr__定义为__str__在此上下文中是不正确的。__repr__在表示对象时应该是明确的。一般来说，它们看起来像<Slot ...>。__str__用于漂亮的打印(正如您定义的那样)
• get_type很奇怪。在Python中，我们通常不做getter和setter。相反，使用属性装饰器。不过，通常大多数人只是将值公开为常规属性(因为使用属性语法是冗长的)。
• 由于Slot是不可变的，因此成为namedtuple似乎是个不错的人选。这提供了不可变的属性和免费的__repr__。
• “私有”属性以_作为指示符作为前缀
• 逻辑问题:为什么add_course([])要返回False？似乎空类应该是可寻址的？这使我想到：
• 您的Course是对象和构建器模式之间的合并。两者同时发生。这很麻烦，因为通常情况下，在类型化语言中，一旦您能够new一个对象，它就应该完全构建(并准备使用)。我不需要thing = SomeThing(); thing.setupMoreStuff()。实际上，我建议把Course也变成namedtuple。添加一个名为@classmethod的create，用于使用给定的name和slots构建Course (也许这可以将至少有一个时隙的assert )。Slot不需要第一个course参数，因此您可以删除循环依赖项。在我看来，理想的语法如下：

class Course(namedtuple('Course', ('name', 'occurances'))):
    @classmethod
    def create(cls, name, slots):
        occurances = defaultdict(list)
        for slot in slots:
            occurances[slot.group].append(slot)

        return cls(name, occurances)

    # ... define __str__ ...

Slot = namedtuple('Slot', ('group', 'day', 'periods', 'type'))

# Example Usage:
algorithms_course = Course.create('Algorithms', [
    # NOTE: Why are the groups 1 indexed!!
    # Note: The periods tuple is confusing.
    Slot(1, Workday.Saturday, (1, 2), 'Lecture'),
    Slot(1, Workday.Saturday, (3, 4), 'Lecture'),
    Slot(1, Workday.Sunday, (3, 4), 'Lab'),
    Slot(2, Workday.Saturday, (1, 2), 'Lecture'),
    Slot(2, Workday.Monday, (1, 2), 'Lecture'),
    Slot(2, Workday.Tuesday, (1, 2), 'Lab'),
])

• 类似于之前的check_slot和add_course舞蹈在Timetable并不是超级丙酮。add_slot应该尝试在无法添加的情况下添加并引发一个特殊的异常，如ScheduleConflictError。您仍然可以使用这两个单独的方法，但我会将check_slot设置为“私有”(使用_前缀)。
• 将句点定义为元组会使check_slot感到困惑。我把句点命名为namedtuples，并添加了一个overlaps()方法。然后_check_slot()变成一行：return any(slot.overlaps(other_slot) for other_slot in self.work_days[slot.day])
• namedtuples还为它们提供了一个默认排序，它将按第一个元素排序，然后再按第二个元素排序(这是您希望在print_timetable中排序的周期)。然后，您可以在__lt__上定义Slot，然后排序用于打印的插槽就是sorted(self.work_days[day]) (与.sort()相比，它更倾向于改变底层列表，除非这是您想要的)
• 同样，在print_timetable中更喜欢string.join和f-字符串。
• 在generate_best_timetables：中
  • 除了常量以外，永远不要使用UPPER_SNAKE_CASE
  • 更喜欢x is None而不是not x
  • 我不会维护best_tt和total_tt，而是维护一个list。当你发现append()和列表有关联的时候。当你找到一个更好的clear()列表。我把这个收藏品叫做best_timetables。我们不喜欢缩写。您可以像这样比较总天数：best_timetables[0].total_days()：

best_timetables = deque()

# ... snip ...

if valid:
    try:
        if tt.total_days() < best_timetables[0].total_days():
            best_timetables = [tt]
        elif tt.total_days() == best_timetables[0].total_days():
            best_timetables.append(tt)
    except IndexError:
        best_timetables = [tt]

- I wouldn't use `tt`. `current_timetable` is better.
- You don't need the `int(val)`. `val` is already an int
- The `valid` flag isn't very pythonic. And if you take my advice about raising `ScheduleConflictErorr`, then you can remove it and do the much more pythonic:

best_timetables = []

for p in product(range(max_group_num), repeat=len(courses)):
    try:
        current_timetable = Timetable()

        # NOTE: Prefer zip() to indexing
        for course, val in zip(courses, p):  # NOTE: name p better, what is it?
            timetable.add_course(course.occurances[val + 1])  # NOTE: val + 1 is still unclear, better naming may help here

        try:
            if tt.total_days() < best_timetables[0].total_days():
                best_timetables = [tt]
            elif tt.total_days() == best_timetables[0].total_days():
                best_timetables.append(tt)
        except IndexError:
            best_timetables = [tt]
    except ScheduleConflictError:
        pass

- Generate your `courses` inside `main()` right before `courses`!

• 这个文件应该被称为college_schedule.py而不是CollegeSchedule.py