Mixing
![Difficulty in this Olympiad problem [closed]](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhZCTB4-bb-s-32SAm6ytjzFOU06cH9o8q-a_wq_UnH6lcd8hvws23CmBWHM6g256LzTX9yK1EiCCzTC1NSgtxlNk_J9hdr9bA3tD0Nqntbl521j4bLAm_uXPANuWLBhcCKTKzns2gaUodx/s72-c/1.jpg)
School timetabling, is there a formula / solution to avoid clashes?
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
I'm a software developer working at a college trying to create an in-house solution to the problem of making sure when a student chooses their three courses that they don't clash on the timetable.
The timetable has 6 blocks throughout the week (A to F), a course takes up one block and cannot have another course with it in the same block. Some courses are available in multiple blocks (Maths for example is in B,C & E, Biology in A & D - the most a course is available is in three different blocks) making it easier for a student wishing to choose those courses. But some courses are only in one block (they aren't popular enough for the need of more classes) and as such they cannot be in the same combination as another course that is only available in that same block (Physics and RE are both in block A for example). Below is an example of three courses that don't work because two subjects are only in block F:
analysis logic
asked Jul 17 at 7:57
tonyyeb
1033
add a comment |Â
up vote
0
down vote
favorite
I'm a software developer working at a college trying to create an in-house solution to the problem of making sure when a student chooses their three courses that they don't clash on the timetable.
The timetable has 6 blocks throughout the week (A to F), a course takes up one block and cannot have another course with it in the same block. Some courses are available in multiple blocks (Maths for example is in B,C & E, Biology in A & D - the most a course is available is in three different blocks) making it easier for a student wishing to choose those courses. But some courses are only in one block (they aren't popular enough for the need of more classes) and as such they cannot be in the same combination as another course that is only available in that same block (Physics and RE are both in block A for example). Below is an example of three courses that don't work because two subjects are only in block F:
analysis logic
asked Jul 17 at 7:57
tonyyeb
1033
1
This seems more akin to an algorithmic analysis problem, and is going to be computational. While I'll admit my knowledge of computational complexity classes is lacking, I'm guessing a polynomial or almost-polynomial time algorithm should be possible in this case
– Brevan Ellefsen
Jul 17 at 8:02
1
This seems related to the exact cover problem. I don't know enough to be able to give you an algorithm just like that (or even whether this is exactly the exact cover problem or not, without at least thinking for a bit), but it may be worth reading up on in any case.
– Arthur
Jul 17 at 8:06
To expand on my previous comment, after some though: Each cross in the table above covers one course and one block. You want to pick crosses so that each course is covered exactly once, and each block is covered at most once. Adding in "phantom" crosses for each block which only covers one block each makes this an exact cover problem. The exact cover problem in NP-complete, though, so that doesn't help much. If we could reduce the exact cover problem to this one, thoguh, at least we would know it's NP complete.
– Arthur
Jul 17 at 8:19
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
I'm a software developer working at a college trying to create an in-house solution to the problem of making sure when a student chooses their three courses that they don't clash on the timetable.
The timetable has 6 blocks throughout the week (A to F), a course takes up one block and cannot have another course with it in the same block. Some courses are available in multiple blocks (Maths for example is in B,C & E, Biology in A & D - the most a course is available is in three different blocks) making it easier for a student wishing to choose those courses. But some courses are only in one block (they aren't popular enough for the need of more classes) and as such they cannot be in the same combination as another course that is only available in that same block (Physics and RE are both in block A for example). Below is an example of three courses that don't work because two subjects are only in block F:
analysis logic
asked Jul 17 at 7:57
tonyyeb
1033
I'm a software developer working at a college trying to create an in-house solution to the problem of making sure when a student chooses their three courses that they don't clash on the timetable.
The timetable has 6 blocks throughout the week (A to F), a course takes up one block and cannot have another course with it in the same block. Some courses are available in multiple blocks (Maths for example is in B,C & E, Biology in A & D - the most a course is available is in three different blocks) making it easier for a student wishing to choose those courses. But some courses are only in one block (they aren't popular enough for the need of more classes) and as such they cannot be in the same combination as another course that is only available in that same block (Physics and RE are both in block A for example). Below is an example of three courses that don't work because two subjects are only in block F:
analysis logic
asked Jul 17 at 7:57
tonyyeb
1033
asked Jul 17 at 7:57
tonyyeb
1033
asked Jul 17 at 7:57
tonyyeb
1033
asked Jul 17 at 7:57
tonyyeb
1033
1033
1
This seems more akin to an algorithmic analysis problem, and is going to be computational. While I'll admit my knowledge of computational complexity classes is lacking, I'm guessing a polynomial or almost-polynomial time algorithm should be possible in this case
– Brevan Ellefsen
Jul 17 at 8:02
1
This seems related to the exact cover problem. I don't know enough to be able to give you an algorithm just like that (or even whether this is exactly the exact cover problem or not, without at least thinking for a bit), but it may be worth reading up on in any case.
– Arthur
Jul 17 at 8:06
To expand on my previous comment, after some though: Each cross in the table above covers one course and one block. You want to pick crosses so that each course is covered exactly once, and each block is covered at most once. Adding in "phantom" crosses for each block which only covers one block each makes this an exact cover problem. The exact cover problem in NP-complete, though, so that doesn't help much. If we could reduce the exact cover problem to this one, thoguh, at least we would know it's NP complete.
– Arthur
Jul 17 at 8:19
add a comment |Â
1
This seems more akin to an algorithmic analysis problem, and is going to be computational. While I'll admit my knowledge of computational complexity classes is lacking, I'm guessing a polynomial or almost-polynomial time algorithm should be possible in this case
– Brevan Ellefsen
Jul 17 at 8:02
1
This seems related to the exact cover problem. I don't know enough to be able to give you an algorithm just like that (or even whether this is exactly the exact cover problem or not, without at least thinking for a bit), but it may be worth reading up on in any case.
– Arthur
Jul 17 at 8:06
To expand on my previous comment, after some though: Each cross in the table above covers one course and one block. You want to pick crosses so that each course is covered exactly once, and each block is covered at most once. Adding in "phantom" crosses for each block which only covers one block each makes this an exact cover problem. The exact cover problem in NP-complete, though, so that doesn't help much. If we could reduce the exact cover problem to this one, thoguh, at least we would know it's NP complete.
– Arthur
Jul 17 at 8:19
1
1
This seems more akin to an algorithmic analysis problem, and is going to be computational. While I'll admit my knowledge of computational complexity classes is lacking, I'm guessing a polynomial or almost-polynomial time algorithm should be possible in this case
– Brevan Ellefsen
Jul 17 at 8:02
This seems more akin to an algorithmic analysis problem, and is going to be computational. While I'll admit my knowledge of computational complexity classes is lacking, I'm guessing a polynomial or almost-polynomial time algorithm should be possible in this case
– Brevan Ellefsen
Jul 17 at 8:02
1
1
This seems related to the exact cover problem. I don't know enough to be able to give you an algorithm just like that (or even whether this is exactly the exact cover problem or not, without at least thinking for a bit), but it may be worth reading up on in any case.
– Arthur
Jul 17 at 8:06
This seems related to the exact cover problem. I don't know enough to be able to give you an algorithm just like that (or even whether this is exactly the exact cover problem or not, without at least thinking for a bit), but it may be worth reading up on in any case.
– Arthur
Jul 17 at 8:06
To expand on my previous comment, after some though: Each cross in the table above covers one course and one block. You want to pick crosses so that each course is covered exactly once, and each block is covered at most once. Adding in "phantom" crosses for each block which only covers one block each makes this an exact cover problem. The exact cover problem in NP-complete, though, so that doesn't help much. If we could reduce the exact cover problem to this one, thoguh, at least we would know it's NP complete.
– Arthur
Jul 17 at 8:19
To expand on my previous comment, after some though: Each cross in the table above covers one course and one block. You want to pick crosses so that each course is covered exactly once, and each block is covered at most once. Adding in "phantom" crosses for each block which only covers one block each makes this an exact cover problem. The exact cover problem in NP-complete, though, so that doesn't help much. If we could reduce the exact cover problem to this one, thoguh, at least we would know it's NP complete.
– Arthur
Jul 17 at 8:19
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
2
down vote
accepted
If you are asking this is a concrete problem, and haven't simplified it very strongly, then almost certainly the easiest solution is to simply loop over every triple $(a, b, c)$ of blocks, check that $a, b, c$ are all different, and check that the student's first choice is available in block $a$, the student's second choice is available in block $b$, and the third choice available in block $c$. This is a very inefficient solution from a formal computational complexity perspective, but for the kinds of numbers you are likely to be dealing with in a realistic schedule, this will be more than fast enough on any computer.
A trivial speed-up would be to let $a$ run only over the blocks in which the first course selected is available, and similarly for $b, c$ and the other two courses. Then you just have to check that $a, b, c$ are all distinct.
A slightly more advanced approach would use Hall's marriage theorem: if each course has at least one block available, there are no two courses among the three which are only offered in a single block which is the same, and if the three courses together are offered in at least three blocks total, then it is possible to schedule the courses. (Note that the example in your image fails the second condition: there are two courses which are only offered in a single block, and it is the same block for both of them.)
answered Jul 17 at 8:12
Mees de Vries
13.7k12345
Thanks for that. We thought a loop was going to give us an answer (eventually) and as you say there aren't that many possibilities to test against so it isn't going to be a long process.
– tonyyeb
Jul 17 at 8:16
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
accepted
If you are asking this is a concrete problem, and haven't simplified it very strongly, then almost certainly the easiest solution is to simply loop over every triple $(a, b, c)$ of blocks, check that $a, b, c$ are all different, and check that the student's first choice is available in block $a$, the student's second choice is available in block $b$, and the third choice available in block $c$. This is a very inefficient solution from a formal computational complexity perspective, but for the kinds of numbers you are likely to be dealing with in a realistic schedule, this will be more than fast enough on any computer.
A trivial speed-up would be to let $a$ run only over the blocks in which the first course selected is available, and similarly for $b, c$ and the other two courses. Then you just have to check that $a, b, c$ are all distinct.
A slightly more advanced approach would use Hall's marriage theorem: if each course has at least one block available, there are no two courses among the three which are only offered in a single block which is the same, and if the three courses together are offered in at least three blocks total, then it is possible to schedule the courses. (Note that the example in your image fails the second condition: there are two courses which are only offered in a single block, and it is the same block for both of them.)
answered Jul 17 at 8:12
Mees de Vries
13.7k12345
Thanks for that. We thought a loop was going to give us an answer (eventually) and as you say there aren't that many possibilities to test against so it isn't going to be a long process.
– tonyyeb
Jul 17 at 8:16
add a comment |Â
up vote
2
down vote
accepted
If you are asking this is a concrete problem, and haven't simplified it very strongly, then almost certainly the easiest solution is to simply loop over every triple $(a, b, c)$ of blocks, check that $a, b, c$ are all different, and check that the student's first choice is available in block $a$, the student's second choice is available in block $b$, and the third choice available in block $c$. This is a very inefficient solution from a formal computational complexity perspective, but for the kinds of numbers you are likely to be dealing with in a realistic schedule, this will be more than fast enough on any computer.
A trivial speed-up would be to let $a$ run only over the blocks in which the first course selected is available, and similarly for $b, c$ and the other two courses. Then you just have to check that $a, b, c$ are all distinct.
A slightly more advanced approach would use Hall's marriage theorem: if each course has at least one block available, there are no two courses among the three which are only offered in a single block which is the same, and if the three courses together are offered in at least three blocks total, then it is possible to schedule the courses. (Note that the example in your image fails the second condition: there are two courses which are only offered in a single block, and it is the same block for both of them.)
answered Jul 17 at 8:12
Mees de Vries
13.7k12345
Thanks for that. We thought a loop was going to give us an answer (eventually) and as you say there aren't that many possibilities to test against so it isn't going to be a long process.
– tonyyeb
Jul 17 at 8:16
add a comment |Â
up vote
2
down vote
accepted
up vote
2
down vote
accepted
If you are asking this is a concrete problem, and haven't simplified it very strongly, then almost certainly the easiest solution is to simply loop over every triple $(a, b, c)$ of blocks, check that $a, b, c$ are all different, and check that the student's first choice is available in block $a$, the student's second choice is available in block $b$, and the third choice available in block $c$. This is a very inefficient solution from a formal computational complexity perspective, but for the kinds of numbers you are likely to be dealing with in a realistic schedule, this will be more than fast enough on any computer.
A trivial speed-up would be to let $a$ run only over the blocks in which the first course selected is available, and similarly for $b, c$ and the other two courses. Then you just have to check that $a, b, c$ are all distinct.
A slightly more advanced approach would use Hall's marriage theorem: if each course has at least one block available, there are no two courses among the three which are only offered in a single block which is the same, and if the three courses together are offered in at least three blocks total, then it is possible to schedule the courses. (Note that the example in your image fails the second condition: there are two courses which are only offered in a single block, and it is the same block for both of them.)
answered Jul 17 at 8:12
Mees de Vries
13.7k12345
If you are asking this is a concrete problem, and haven't simplified it very strongly, then almost certainly the easiest solution is to simply loop over every triple $(a, b, c)$ of blocks, check that $a, b, c$ are all different, and check that the student's first choice is available in block $a$, the student's second choice is available in block $b$, and the third choice available in block $c$. This is a very inefficient solution from a formal computational complexity perspective, but for the kinds of numbers you are likely to be dealing with in a realistic schedule, this will be more than fast enough on any computer.
A trivial speed-up would be to let $a$ run only over the blocks in which the first course selected is available, and similarly for $b, c$ and the other two courses. Then you just have to check that $a, b, c$ are all distinct.
A slightly more advanced approach would use Hall's marriage theorem: if each course has at least one block available, there are no two courses among the three which are only offered in a single block which is the same, and if the three courses together are offered in at least three blocks total, then it is possible to schedule the courses. (Note that the example in your image fails the second condition: there are two courses which are only offered in a single block, and it is the same block for both of them.)
answered Jul 17 at 8:12
Mees de Vries
13.7k12345
answered Jul 17 at 8:12
Mees de Vries
13.7k12345
answered Jul 17 at 8:12
Mees de Vries
13.7k12345
answered Jul 17 at 8:12
Mees de Vries
13.7k12345
13.7k12345
Thanks for that. We thought a loop was going to give us an answer (eventually) and as you say there aren't that many possibilities to test against so it isn't going to be a long process.
– tonyyeb
Jul 17 at 8:16
add a comment |Â
Thanks for that. We thought a loop was going to give us an answer (eventually) and as you say there aren't that many possibilities to test against so it isn't going to be a long process.
– tonyyeb
Jul 17 at 8:16
Thanks for that. We thought a loop was going to give us an answer (eventually) and as you say there aren't that many possibilities to test against so it isn't going to be a long process.
– tonyyeb
Jul 17 at 8:16
Thanks for that. We thought a loop was going to give us an answer (eventually) and as you say there aren't that many possibilities to test against so it isn't going to be a long process.
– tonyyeb
Jul 17 at 8:16
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2854272%2fschool-timetabling-is-there-a-formula-solution-to-avoid-clashes%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
1
This seems more akin to an algorithmic analysis problem, and is going to be computational. While I'll admit my knowledge of computational complexity classes is lacking, I'm guessing a polynomial or almost-polynomial time algorithm should be possible in this case
– Brevan Ellefsen
Jul 17 at 8:02
1
This seems related to the exact cover problem. I don't know enough to be able to give you an algorithm just like that (or even whether this is exactly the exact cover problem or not, without at least thinking for a bit), but it may be worth reading up on in any case.
– Arthur
Jul 17 at 8:06
To expand on my previous comment, after some though: Each cross in the table above covers one course and one block. You want to pick crosses so that each course is covered exactly once, and each block is covered at most once. Adding in "phantom" crosses for each block which only covers one block each makes this an exact cover problem. The exact cover problem in NP-complete, though, so that doesn't help much. If we could reduce the exact cover problem to this one, thoguh, at least we would know it's NP complete.
– Arthur
Jul 17 at 8:19