4 replies to this topic

[rage85]

Hi all,
I am new to this forum. I am faced with a programming challenge.
I need to write a program which produces a school schedule. The inputs to the program would be number of classes, subjects for each class, the teachers and the subjects they can teach and their availability. The output would be all possible schedules.
An easy solution would of course be a brute force algorithm using recursion but this gets out of hand even for small number of classes and subjects. Can anyone give me a better idea of how to go about handling this to create a program that runs in reasonable time? I would greatly appreciate any help and insight.

Thanks.

[WingedPanther]

"All possible schedules" sounds like a red flag to me. Generally, there will be thousands, or hundreds of thousands, of possible schedules for even a tiny number of teachers. What kind of input are you talking about, and why do you need all possible schedules?

[rage85]

Thanks for your answer.
You are correct that there will be many many schedules. The reason I need all possible schedules is that it is possible that only a handful of those schedules actually work. i.e. from millions of schedules I generate maybe only 10 actually are perfect (based on some criteria). However to get to that 10, I have to try all possibilities, no?

[wim DC]

Even though there may be thousands of records in the database you don't have to get them all out of the Database and show it all.
Use paging where you show like 25 / page. Give the user the ability to filter and sort and they shouldn't be complaining.

It's a bit easier with an Oracle DB as you got ROWNUM you can select there, with mysql it's a custom variable where you do +1, see Displaying row number (rownum) in MySQL « Jim's Life
Selecting 25 records from the database goes blazing fast and it satisfies the users.

Don't forget to do a Count(*) to know how many pages you should have for the paging.

[WingedPanther]

rage85 said:

Thanks for your answer.
You are correct that there will be many many schedules. The reason I need all possible schedules is that it is possible that only a handful of those schedules actually work. i.e. from millions of schedules I generate maybe only 10 actually are perfect (based on some criteria). However to get to that 10, I have to try all possibilities, no?

No. Often, you can quickly detect a violation early in the recursive build of the schedule and throw out thousands of possibilities without fully generating them. Further, depending on what the restrictions are, you may be able to quickly build the viable solutions from the restrictions. You may want to look into Prolog as a good language for this type of problem.