Programming help.

[mmmdreg]

Please anyone who is a competant ( ?) coder look at my problem! Please first see the attached picture so you'll know what I'm on about.

Now, all the black boxes are "subjects", and the columns are all the "lines" that the subjects can possibly fit in. I have to be able to check every combination of subjects against a datafile of the subjects each student has chosen to minimise the amount of clashes.

To do this, I want to write the position of every subject for every combination to a file. How would this be done assuming any data you want is in an array and more importantly that the number of black boxes is a variable, whereas the columns are a constant (7)

 

[sonofslim]

is each line a distinct set of subjects? (ie, "COMB|2" is only going to show up in column 1, not any other column)
if that's the case, then really it's just one problem (find all permutations of an array) done 7 times with different data sets.

 

[mmmdreg]

is each line a distinct set of subjects? (ie, "COMB|2" is only going to show up in column 1, not any other column)
if that's the case, then really it's just one problem (find all permutations of an array) done 7 times with different data sets.

No. Every subject can go any any column. Which makes it a little harder..

 

[robbieduncan]

In general scheduling problems are NP hard. This means that they are not really solvable. The best general scheduling solution I know of is to use a genetic algorithm, which I you can't write this you won't be able to write either!

I find your requirements a bit confusing. You have a file on disk with a list of students (I don't know say 1000). For each student there is a list of classes they have chosen (is there some sort of limit on the number of classes each student can choose?). You want to find the best arrangement of classes in time slots so as there are least clashes?

 

[mmmdreg]

They can choose a max of 7 subjects and yes, I want to find the best arrangement of classes in time slots so as there are least clashes.. It can be done because I've seen it work. So yeah.. I just don't know how =(

 

[robbieduncan]

Before I give you an answer to what sounds like a homework assignment I think I need to clarify what I was trying to say above. Whilst it is possible to enumerate all the possible arrangements of classes and check each arrangement against the list of student choices this can take an amazingly long time! In many cases it takes so long that it is simply not usable. The genetic algorithm solution cannot guarantee you the best solution but it has a good chance of getting an acceptable solution much more quickly. I will post a "real" answer to your problem in a little bit...

 

[robbieduncan]

Real Answer! I have placed a gziped, tared up XCode project on my iDisk here: schedule.tar.gz

Note that all this achieves is the permutation part. It uses a hard coded array of subjects, you can obviously read your own from disk. This generates a lot of permutations (3 subjects generates over 2000 possible arrangement).

Note that the code will create duplicates.

I hope that it helps!

 

[mmmdreg]

This generates a lot of permutations (3 subjects generates over 2000 possible arrangement).

Note that the code will create duplicates.

I hope that it helps!

Thanx! I'll take a look in a moment. But why are there 2000 possibles from 3 subjects. Shouldn't there be only 7^3? Is that what you meant by "duplicates"?

EDIT: I looked at it. You have 4 subjects hence the 2401 combo's =) 3 generates 343.

Sweet stuff though. Now I'll just make it work for me =P

 

[robbieduncan]

Woops! Basically the duplicates arrise as the code treats the order that the subjects are assigned to each "slot" as important. In reality it does not matter is a single time contains "MATH1, ENG1" or "ENG1,MATH1". It would be relatively easy to filter these out at the end...

 

[mmmdreg]

Woops! Basically the duplicates arrise as the code treats the order that the subjects are assigned to each "slot" as important. In reality it does not matter is a single time contains "MATH1, ENG1" or "ENG1,MATH1". It would be relatively easy to filter these out at the end...

oh yeah. good point now that I think about it. though as the number of subjects change that would change a bit too eh..