First, this really should be asked somewhere like stackoverflow. Software engineering is more than algorithm selection.
This is going to sound strange, but the most easily applicable algorithm (class of algorithms really) to your situation is Linear Programming, or its counterpart Integer Programming. The idea is to encode your constraints as a set of linear equations (perhaps restricted to integer solutions) and apply general-purpose solvers to either find a solution or prove none exist.
- One advantage of this approach is the existence of FOSS solutions expressly designed to solve such problems quickly.
- Another advantage is the ability to tweak your constraints and express many possible ideas without any major tweaks to the algorithm.
One way to go about this would be to define a binary variable x_s,a for each student s and each activity a expressing whether they will be in that activity or not and p_s,a expressing whether they preferred it or not. Then we define a fairly long list of inequalities (these can and should be programatically generated).
- To enforce class size limits, for each activity a the sum (x_s1,a)+(x_s2,a)+...+(x_sn,a) can be bounded by your favorite constant.
- To enforce preferences, for each student s you also require that (x_s,a1)+(x_s,a2)+...+(x_s,an) is at least 1, where the ai are restricted to be the activities that student prefers.
- To enforce some sort of fairness, you can have an equation for each pair of students guaranteeing that no student is in more than one more activity than the other (if such balancing is desired).
- To attempt to get full class sizes, you can set the linear objective function you want to optimize to simply be the sum of all the x_sa.
- You'll need some other constraints for realism, for example that all the x_sa are non-negative and that they are bounded above by 1.
If you want more help with this approach, Dr. Nathan Axvig is always looking for new operations research projects. I've talked with him at a couple conferences, and he's knowledgeable and friendly. To quote his bio, "Dr. Axvig is keenly interested in establishing partnerships with businesses, non-profit organizations, and governments with the joint goals of providing his clients with useful solutions as well as giving his students valuable experience working on real real-world problems. To this end, Dr. Axvig has supervised a number of undergraduate consulting projects and is always looking for more."