I have got a Secret Santa assignment project going on. The situation is the following:
We're organizing a university Secret Santa gift exchange. There are 4000 students in the faculty participating.
In their participation, they had the ability to choose one of the following giftee picking options:
- I want to gift to any other student, no matter his faculty
- I want my giftee to be of any other faculty but only if that faculty is under the Science Faculty (Since we're in the computer science department ourselves)
- I want my giftee to be of my own faculty only.
Now, I've been thinking of a way to abstract this problem to something else, so I can solve it. I've got the list of imaginary participants, and the problem smelled like Graph theory, so I organized it into a Graph (with JGraphT).
Now, every participant is a node in my graph.
The problems are:
- I was thinking of putting Edges from every participant to another if the gifting operation is valid (e.g. someone that wants to gift to any faculty will have connections to all other 3999 participants), but that operation is expensive and slow as heck. I'll end up with around a million edges, 1.6m if every participant decides to be generous. Is this something I just have to accept? I don't even think my computer has enough RAM to store all that during implementation! EDIT: I was being stupid. My graph is omnidirectional and I wasn't checking for already existing edges when creating new, as edge(vertex0, vertex3) would be the same as edge(vertex3, vertex0). With a simple if-check, my graph is now built and very manageable. Please disregard this.
- If I take the hit and end up building the edged Graph (EDIT: Which I did), what problem can I abstract it to, so I can pick an algorithm and solve it? Is this a Stable Marriage problem? An assignment problem?
Any help would be appreciated. Have a good holiday.