Turning generative recursion results (leaves of a tree) into connected components (where each neighbour differs by one element)

Question

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.

For example:

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/

Answer 1

EDIT My initial interpretation was clearly incorrect although some of the content may be useful to someone so I'll leave it at the bottom of all this.

With that, it seems like each step further into the tree will lead you to a mutually exclusive path (e.g. timetables can't have $A_1$ and $A_2$). This split is what we can call a "decision point". Assuming all your leaf-node timetables are stored in a list, you could figure out where the decision point was, and then bounce over to the corresponding node with the alternate decision.

Example: Let's say, similar to your example we have courses $A$ and $B$, with sections $A_1, A_2, A_3, B_1, B_2$. We then get a decision tree:

You can see the decision point of course $A$ is at the first level. Similarly you see the decision point of course $B$ is at the second level. The red line in there represents an example of two timetables that differ only by their grandparent, rather than just their parent. We can use some math and indexing to figure out how they're related.

As long as your course decision at each level is consistent, we can use some math and indexing to figure this out pretty easily.

Let's say you have $n$ courses: $c_1, c_2, \dots, c_n$.

Now let's define the size of a course as the number of sections = $|c_i|$.

It's pretty clear to see that, in the end, the number of leaf node timetables we'll have is $m = \prod_{i=1}^n |c_i|$. Let's assume courses are decided in increasing order (i.e. $c_1$ is decided at level 1 in the decision tree, $c_2$ is decided at level 2, etc.). If your leaf nodes are contained in a list, we can easily find related nodes based on the level of a particular course decision.

Let's say we look at leaf node timetable $j$. If we want to find all timetables that only differ at course $i$, we know they will be $\frac{m}{\prod_{k = 1}^i |c_k|}$ away.

An example might help, it's extremely clear if we're only dealing with a binary tree (each course has 2 sections). Let's say we have 3 courses: $A, B, C$. We then end up with a list of leaf nodes:

$$\left[(A_1, B_1, C_1), (A_1, B_1, C_2), (A_1, B_2, C_1), (A_1, B_2, C_2), (A_2, B_1, C_1), (A_2, B_1, C_2), (A_2, B_2, C_1), (A_2, B_2, C_2)\right]$$

We can represent these in binary:

$$\left[000, 001, 010, 011, 100, 101, 110, 111\right]$$

If we wanted to find where $111$ differs at course $B$. We find the distance between them is:

$$ \begin{align} d & = \frac{m}{\prod_{k = 1}^i |c_k|}\\ & = \frac{8}{\prod_{k = 1}^2 |c_k|}\\ & = \frac{8}{2 \cdot 2}\\ & = 2\\ \end{align} $$

Now deciding whether to subtract or add this distance is left up to simple edge case handling. But we see that 2 indices away from $111$ is $101$, which is the difference at course $B$ we were looking for. You should be able to take this approach to determine each differing timetable without having to compare everyone.

Misinterpretted Response Below

This algorithm seems similar to itemset lattice generation in association rule mining. Not the actual machine learning part, just the itemset generation. With this in mind, memoization in general would help downsize the repeated timetables. If you find that a child subproblem has already been solved, you can link the parent to that memoized solution, reducing the amount of links in your tree while keeping the children/parent connections consistent.

Memoization could also help with the "one section swap" connection. You already know all siblings will be "one section swap" connections. From there, it's simple to see that all leaf siblings will be connected. Using memoization these leaf-to-leaf sibling relationships will be much tighter and should basically figure themselves out.

Let's take an example with 5 sections $A, B, C, D, E$, assume a timetable is full when it gets 3 courses and just to add some variation let's say section $A$ conflicts with section $E$. If my understanding is correct your graph should look like the following, where green edges are "memoized" edges from parent to memoized child. Red crossed nodes are conflicting timetables.

Then, you may notice that we can construct a sibling graph of the leaf nodes:

Interestingly (but expected) the sibling graph connects all valid complete timetables and all connections are "one section swap" connections! So I definitely think memoization is the way to go.