I have no clue on what keywords I could use for searching. So perhaps someone here recognises this problem.

I have 18 courses that I have to put in a schedule of 3 blocks, 6 chourses per block. Every time I put two courses in one block, there might be a cost (one or more students want to attend both courses). I know how to calculate the whole cost.

I only need a clever algo that goes through some ways of placing the courses in the blocks. I guess I don't have resources to go through all possibilities. It could look like this:

A B C D E F
G H I J K L
M N O P Q R

I'd calculate the cost of this and save the schedule and the cost. Then I'd advance to the next combination, switching two courses from different rows, calculate the cost and save the combination, if the cost was smaller. Then advance, hopefully taking heuristic steps.

So first of all I'd need a simple algo for switching courses, secondly a more clever algo to not have to go through all possibilities.

<edit />

Brute force would mean going through all possibilities. Seems all possibilities would be too much. Picking 6 of 18 for the first row would be 13 million possibilities. Picking 6 of the 12 that are left, for the 2nd row, would be 665,280 possibilities. Alltogether 10¹² possibilities, which is too much to parse through.

But I still need the parsing algo, because I can divide the problem into first sorting half of all the courses, like A, B, C, G, H, I, M, N and O, which gives me 60,000 possibilities to run through. After that I can fixate them, then I run another 60,000 possibilities for the remaining courses.

<edit />
I spent some time to find an algo for dealing with these three sets, until I saw the light. It's all about picking out k elements from n elements. I parse through all combinations of three out of nine. For each, I parse through all combinations of three out of the six remaining elements. And the search words were "Generating Combinations of a Set of Elements".

He was asking for a decent algo.

I'm not sure I'm following where your numbers come from -- perhaps I don't understand the problem being solved. My understanding was that the scoring was based just on the set that each course is in, but not their order. So for that you'd have 18C6 combinations for the first set, and 12C6 combinations remaining for the second. (The final set would then already be determined by this: 6C6=1.)

Assuming I ran my numbers correctly, you still have to build and score 17,153,136 permutations. While this can probably be run relatively quickly in the grand scheme of things, having a smarter algorithm might prove to be helpful.

And to derail this thread now, suppose that you had much large values that you wanted to optimize the problem for. For example, there are 6 sets and 36 courses. You're then looking at an impossible to brute-force problem to be solved. An approach that I've wanted to take for this in the past -- though never implemented -- was using a genetic algorithm to optimize the score. That might be something worth looking into.

I believe you are mistaken. The algorithm for the binomial coefficient "n choose k" is:

With that in mind, it sounds like you're taking the same approach here that I did. So for the first set you have this many combinations:

Then you have 12C6 combinations for the remaining two sets:

Multiplying these together, you get the total number of permutations to examine:

Regarding the actual problem that you have to solve, I haven't put any thought into it yet.

Go pick up a book on combinatorics.
I don't have time to explain it all right now.

I've thought about this deeply. I found 'the same' to be a confusing way of thinking
about the problem.
So, not really disagreeing or agreeing, but I can give a fairly clear overview of the situation :-

For each unique Choice of Six Courses , which is a set of 6 numbers, there are 6! = 720 different versions of copies of the Set, each with the numbers arranged in a different order.

The 6! comes from what you said :

NOW

Total ways of choosing 6 - not discounting a 'way', if the numbers are the same as another way but ordered differently :

18*17*16*15*14*13 = 13366080

One Unique way is included in the count 6! = 720 times

13366080 = 18564 * 720

i.e There are 18564 lots of 720 sets of six numbers which are the same sets because only the order of numbers is different.

So there are 18564 Unique sets of 6 different numbers (or courses).

Does that help?

/* EDIT */

I guess, you might not like the different context of the word set here (I mean mathematical set, not set at a school).

In maths, a set is defined with curly brackets and a set of n elements is the same set regardless of what order the elements are in.

So for example the mathemtical set of 3 elements { 3, 6, 7 } is the same as { 7, 3, 6}.

When I was at school there were two sets for all the sciences. Set 1 and Set 2.
The brighter students where in set 1.

Essentially though a school set and a set of numbers are both mathematical sets
: a collection of objects.

Are those stickers still available?

Great.

Hope things work out well.

It started with students choosing courses for next year. They chose three courses plus some in reserve. According to their choices, we decide which courses to run and which to skip. We can't afford courses with only 2 or 3 students.

After that I ended up in 18 groups to be placed in 3 blocks, 6 groups in each block. Most groups are individual courses, but some are one course divided in two groups (finally there were about 12 different courses).

At this point, my algo kicks in. I pick 6 groups for each block and calculate the cost. One cost unit is one student that have chosen two courses that are placed in the same block. The more such students, the more it costs to put those two groups in same block. If one of the courses runs in another group in another block, too, it halves the cost. If both courses run in another groups in other blocks, the cost is again halved. So when I have 6 groups in one block, I check each combination of two groups (6C2) and add the total cost. And add it to the costs of the other two blocks.

After finding the optimal combination of blocks and groups, we let the students pick one group from each block (everyone has to pick three courses). This seems to cause a mess. Actually we do have software that could optimize this step, placing each student in the right group according to their choices, but our headmaster decided to let the students pick their groups. Before we've got everything sorted, I'm afraid we will have to ignore the choices the students did in this second turn and try to optimize the groups using the software we have. But the software we have couldn't do this first step that I did with my algo.

<edit />

Ok, it went well. The students picked their courses from the three blocks. It looked like this:

{"name":"609284","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/8\/3\/8350036aaacf3557ccb548c46f1e4e5b.png","w":393,"h":207,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/8\/3\/8350036aaacf3557ccb548c46f1e4e5b"}

The black boxes mark the selected courses for one student. (Red and blue are only code colours for different types of courses. Irrelevant.)

It worked very well for one school. But my next project will be to use same ideas for another school, where one student has to select about 25 courses for one year. For each schedule they pick 5-6 courses. Compared to the three block schedule above, these students have 7 blocks. Each block can hold 6-8 courses. No way I could use same algo!

I'd need a different approach, some heuristic algo. I'd start by placing courses in blocks, one by one. For each course, I'd place the course in a block with least costs. If there are several blocks with no cost at all, I'd place the course in the one with most courses. Because we aim to fill blocks with as many students as possible.

After all courses are placed, there would still be much to check and try out. Now each course costs something! Even the ones that costed nothing in the first place, because now the cost is caused by courses added later. I'd like to try the following:

1. Pick away one course that causes the biggest reduction of the total cost

2. Place the course in a new block, where it causes the least cost

3. Repeat from #1 until the course that you try to place would go back into the same block

4. Try further rescheduling with other courses causing large costs

In #1 I could create an ordered list of say 5 courses causing the biggest costs and I'd operate with the first course. In #4 I'd pick the second course from the list.
This could go on forever, don't know. But at any time, the next step should give a solution with a little bit improved schedule.