Programming help.

Discussion in 'Mac Apps and Mac App Store' started by mmmdreg, Apr 16, 2004.

  1. mmmdreg macrumors 65816

    mmmdreg

    Joined:
    Apr 14, 2002
    Location:
    Sydney, Australia
    #1
    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)
     

    Attached Files:

    • pic.JPG
      pic.JPG
      File size:
      28.3 KB
      Views:
      100
  2. sonofslim macrumors 6502a

    sonofslim

    Joined:
    Jun 6, 2003
    #2
    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.
     
  3. mmmdreg thread starter macrumors 65816

    mmmdreg

    Joined:
    Apr 14, 2002
    Location:
    Sydney, Australia
    #3
    No. Every subject can go any any column. Which makes it a little harder..
     
  4. robbieduncan Moderator emeritus

    robbieduncan

    Joined:
    Jul 24, 2002
    Location:
    London
    #4
    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?
     
  5. mmmdreg thread starter macrumors 65816

    mmmdreg

    Joined:
    Apr 14, 2002
    Location:
    Sydney, Australia
    #5
    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 =(
     
  6. robbieduncan Moderator emeritus

    robbieduncan

    Joined:
    Jul 24, 2002
    Location:
    London
    #6
    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...
     
  7. robbieduncan Moderator emeritus

    robbieduncan

    Joined:
    Jul 24, 2002
    Location:
    London
    #7
    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!
     
  8. mmmdreg thread starter macrumors 65816

    mmmdreg

    Joined:
    Apr 14, 2002
    Location:
    Sydney, Australia
    #8
    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
     
  9. robbieduncan Moderator emeritus

    robbieduncan

    Joined:
    Jul 24, 2002
    Location:
    London
    #9
    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...
     
  10. mmmdreg thread starter macrumors 65816

    mmmdreg

    Joined:
    Apr 14, 2002
    Location:
    Sydney, Australia
    #10
    oh yeah. good point now that I think about it. though as the number of subjects change that would change a bit too eh..
     

Share This Page