I am creating a program that optimises the classes provided by my university for student's timetables.
I parse data into the following structs/classes:
public struct Subject
{
public int Classes {...}
public int Hours { ... }
public string Name { get; set; }
public string Code { get; set; }
public string Base_Code;
public Campus Campus { get; set; }
public Semester Semester;
}
public struct Timeslot
{
public string ClassType; //code for type: i.e. L for Lecture, W for Workshop
public string Description;
public DayOfWeek Day;
public DateTime Start, Finish;
public List<Tuple<string, string>> weekSpans;
public string Location;
}
public struct Class
{
public Subject subject { get; set; }
public Timeslot time { get; set; }
}
Across my n subjects for the semester, I have a total of m mandatory classes to attend (lecture 1, 2, 3, workshop e.t.c). I have these stored in a list of list of type 'Class'.
ex:
Lecture 1 (subject 1)
- class @ 9am Monday
- class @ 1pm Monday
Workshop 1 (subject 2)
- class @ 9am Monday
- class @ 2pm Tuesday
I am currently using Eric Lippert's Cartesian Product method to generate a IEnumerable<IEnumerable<Class>> consisting of all n-class combinations.
static IEnumerable<IEnumerable<T>> CartesianProduct<T>(this IEnumerable<IEnumerable<T>> sequences)
{
// base case:
IEnumerable<IEnumerable<T>> result = new[] { Enumerable.Empty<T>() };
foreach(var sequence in sequences)
{
var s = sequence; // don't close over the loop variable
// recursive case: use SelectMany to build the new product out of the old one
result =
from seq in result
from item in s
select seq.Concat(new[] {item});
}
return result;
}
However, my issue occurs when I need to gather necessary information from each IEnumerable to determine which timetable fits set criteria (shorter days, most days off, e.t.c.). Trying to iterate through all and storing them in my TimeTable container class is really taxing to the memory on top of the memory needed to store the initial permutations.
public class TimeTable
{
public IEnumerable<Class> _classes;
public DateTime MinStart { get; private set; }
public DateTime MaxFinish { get; private set; }
public int DaysOff { get; private set; }
public TimeTable(IEnumerable<Class> Classes) { ... }
}
It is so taxing in fact that my memory skyrockets to 2GB and then crashes. I have thought of optimizing the permutation process by discarding timetables that include clashes, which I know how to do but I cannot figure out where I can put my code into the CartesianProduct algorithm so that it isn't kept in memory. I have also thought of assigning each class an ID and then calculating the permutations however that doesn't optimise the need to sort the timetables by the user's preference.
This is my first personal project where I have to deal with combinatorics and memory optimisation so any advice and help on how I can optimise this optimisation process (ha!) would be much appreciated.
