I'm generating valid timetables for my uni with a simple generative recursion algorithm like this (disregarding handling of course-specific labs and tutorials)
def generate(current_timetable, unallocated_courses): if conflicts(current_timetable): return if not unallocated_courses: results.add(current_timetable) return course = first(unallocated_courses) for section in course: new_timetable = copy(current_timetable) + section generate(new_timetable, rest(unallocated_courses))
(Storing results as a flat list for now)
Probably room for memoization in there, but that part of the program is fast enough already.
Now, since this generates too many timetables to easily compare, I decided to group them into 'families', which are connected undirected graphs of timetables in which you can navigate between any two nodes by swapping one section at a time for another. As a result, I get around ~10 very differently shaped timetables that I can subjectively compare.
My naive O(n^2) approach was to take every single combination of 2 nodes, build an adjacency list based on the delta between each pair, and then find connected components with BFS.
If I store results in a tree (i.e. non-leaves are incomplete timetables, root is empty, each child has 1 more course allocated than its parents, and the leaves are the completed timetables), is there any insight about this structure that could make finding connected components faster?
I realize that immediate siblings would be connected in the final graph, since their only difference is which section (of the course that their parents is missing) was picked, but there can also be leaves that are identical except for e.g. their grandparents, and those are the ones that I can't seem to detect without the O(n^2) approach.
To clarify: Each course has a bunch of sections. At each level of the tree, a certain course is considered, and for each section in that course, a subproblem is created.
At level 1, different sections of course A are considered. At level 2, different sections of course B are considered.
Here's sample output with 2 families (sorry about the current interface): https://dmitry.lol/public/timetablor/