0

I need to create an algorithm where I have two lists of unequal size, called Students and Teachers. There are many more Students than there are Teachers. I need to create a pairing for each Student, where each Teacher is matched with approximately the same number of Students.

The complication is that I have a collection of pairings which are unacceptable. Specifically, each Student may have one or more Teachers with whom he cannot be paired.

I know I could do a very efficient greedy algorithm that just starts matching arbitrarily and skips over matches that don't work, since the number of Students to which each Teacher is assigned doesn't have to be exact. Regardless, I would love an efficient and complete way to do this. Thanks for any advice you can offer!

3
  • Easy enough but which programming language are you working in?
    – Absinthe
    Nov 1, 2016 at 21:42
  • c#, I'm using ASP.NET MVC. The student and teacher lists are given as parameters, and the restrictions are part of the database.
    – hallordylo
    Nov 1, 2016 at 21:44
  • Create a dictionary of unacceptable pairings and compare against that. msdn.microsoft.com/en-us/library/xfhwa508(v=vs.110).aspx
    – Absinthe
    Nov 1, 2016 at 21:49

1 Answer 1

Reset to default
1

I would start from the most limited matching to less limited this will leave the unlimited matching last and you can use them to balance.

1
  • That's a great solution, thanks @O_Z! A lot of students won't have any restrictions at all, so once I get through them I can just run straight through the list.
    – hallordylo
    Nov 1, 2016 at 21:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.