Course schedule using php/mysql

The problem consists of a course scheduler (for university/college). If I am not using SQL: i have one array of arrays and one 2-dimensional array. Each array in the first array contains the unique ids of the different courses i which to take (each course has different times and days represented by these unique ids). The second array contains compatible course (i.e. that don't make a time conflict). If I which to take "n" number of courses I wish to find all the possible combination of the courses without having a time conflict.

+++++++array 1+++++++++   ++++array 2+++++
course1 course2 course3   (compatible ids)
  122     235     654         122  235
  123     456     876         122  456
  124     190     943         122  654
  145     456     321         122  321
                              235  654...

In the above example the foll开发者_如何学Pythonowing ids can make a schedule: 122 235 654.

The only solution I came up with is brute forcing it (n nested loop). Is there a more efficient way of solving this problem? Maybe by using MySQL?

---

If it's an option, I'd definitely use MySQL, and maintain most of your relational data that way.

---

create table course1 ( id INTEGER );
create table course2 ( id INTEGER );
create table course3 ( id INTEGER );
create table compatible ( id1 INTEGER, id2 INTEGER );

select distinct c1.id, c2.id, c3.id
from course1 c1
  INNER JOIN compatible p1 on p1.id1 = c1.id
  INNER JOIN course2 c2 on p1.id2 = c2.id
  INNER JOIN compatible p2 on p2.id1 = c2.id
  INNER JOIN course3 c3 on p2.id2 = c3.id
where exists ( select * from compatible p3 where p3.id1 = c1.id and p3.id2 = c3.id )

This is really not that flexible, and though it should be faster than the full scan (as long as ids are indexed) it would require 2^n constraints, so doesn't scale well to large numbers of courses. Please note that the pairwise order of the compatible table is important.

You can get better performance from your php solution by using hash tables and nested lists. Change the structure of your second array to

array (
    122 => array( 235, 456, 654, 321),
    235 => array( 654...

then a brute force approach can be much more efficient (no full list scans). This should be similar performance to the sql approach. Conflicts can be determined by doing list intersection on smaller subsets.