So, creation of a secret santa program. A simple task you might think. Well, it might well be! Indeed I believe there is an entire application in timetable management and scheduling, which if I was truly aware of, would make this task trivial, or at least tractable!
As it stands, I entered it blindly, produced a naive solution, got burnt, thought about it some more, and got to grips with some really interesting problems. I’ve ended up with a BETTER solution but it still has some problems. Let us share my investigation.
First, the problem, in it’s entirety. A set of X friends (s.t. X E AllFriends) get together every year and have a lovely meal at christmas. If that wasn’t enough loveliness, they also get each other gifts every year! Wonderful! However, things are not as lovely as they might seem. Within X = [x1,x2,x3,...,xn] there lies certain people who shouldn’t really get each other presents. For example x13 and x72 have been dating for years and x20 through x77 live together in some sort of crazy commune! They are getting each other gifts anyway so what the hell is the point of them getting gifts again! Then we come to the actual exchange, we postulate that it is “boring” if xi gets xi a gift, and equally “boring” if xi gets xj a gift and xj gets xi a gift. Fuck that shit.
So, the contraints: * certain people can’t get presents from others * 2 people must not directly give each other a gift * a person can’t give themselves a gift.
The first method that came to mind was the “picking names out of a bag” method. We’ll call that baseline. In that scenario you’d pick a name, if it was invalid for you, you replaced it in the bag, try again. Intuition states that the first person to have a dip would be the person with the most constraints, i.e. with the most names in the bag they can’t have, if you did it any other way it would be far too likely that the last person would end up with no valid names in the bag. We’ll see why intuition is a little fucked up in a moment.
So a solution: create a set of available people, for each person a set of invalid people and finally, hold a set of people already assigned a santa. Pick a person (a santa) with the MOST constraints (i.e. the person who has issue with getting gifts from the most people) and assign them a person to give a gift to (a santee) at random. Now, make the santa an invalid gift giving choice for that selected santee. Do this repeatedly and you’ll either fuck up and end up with 1 person who can’t be assigned, or you’ll have a good selection. Simple, brute force and it WILL break. But so will the baseline solution, and this is easier to run many many times. But if you run this enough you’ll get a matching of people which fits your construct. Good enough right?
FALSE
I’ll explain why when I’ve prettied the data.
0 Comments