My Family's Secret Santa

[devgal89]

So My family does a secret santa or pollyanna game every year. Y'know the one. Everyone draws names out of a basket and you have to get them presents. It saves us money in the long run because theres around 12 or so players, and spending about 150-200 on one person is cheaper and easier than spending 35-50 on 12 people.

But we've been running into a problem. People keep on drawing the same names year after year. My oldest sister has had me for three years running. This happens partially because we want to make sure we do not get ourselves, or our spouse/significant other, so when someone draws one of those names we have to re-draw. This year we did four re-draws before we all got our assignments. We're trying to think of a way to generate the assignments in such a way that it will be impossible to get the same names until there's been a (nearly) complete go-around. I feel like this could very easily be done with a program, but the only programming experience I had was a class that taught ActionScript 3 in flash in college a year or two ago. Helpful, but I haven't programmed enough to be able to sit down and rationally think about how to write a program that can check these parameters that are unique to each person. (example, my sister cannot draw herself, her husband Ron, me, or my sister Maureen, whereas I cannot draw Patrick, Ian, James, or Ron.)

So can anyone think of a way (via programming or otherwise) to be able to do these assignments without having a third party sit down and practically hand pick the assignments?

[Qaanol]

The last time we had a topic about secret santa, the goal was to make sure that, once you knew who your recipient was, you considered everyone aside from yourself as equally likely to be your secret santa; and also the method was guaranteed to finish in finite time, without the possibility of having to “redraw names” perpetually.

This time you want non-repetition of recipients from year to year. The way I see it, you begin with no one having had a previous recipient, so the first year is a normal secret santa, drawn by whatever method you prefer. We can look at an n×n “checkerboard”, with names along the axes, where square (x, y) represents the event “person x is santa for person y”. After Christmas, squares that were used this year get crossed off, and cannot be used next year. Year after year, more squares get crossed off.

At any particular year, we start off with the current checkboard, representing a directed graph of allowed santa-recipient relationships. I do not see a “natural” way to assign names from such a graph, short of making a set of envelopes for every valid assignment of names, putting each set of envelopes in a box, and choosing a box at random using some desirable probability distribution. That’s easy enough to simulate with a computer program, but it’s not “interactive” the way drawing names from a hat is.

Also, having organized a secret santa this year (making use of the “all other participants are equally likely to be my santa” solution from the previous thread), I used a script of my own devising that met the conditions of the previous thread. Its output consisted of one file with the santa-recipient graph, which I have not yet opened, and whole batch of files, one per person, that at the end of the script contained the address of the recipient, and the santa’s name in the filename. That way I was able to send out the address files to the santas, without myself knowing who got whom. But if it becomes necessary, I’ll be able to check.

I’d be interested if there is a “nice” way to assign santas when the possibilities are restricted by who has previously gotten whom, but I’m not sure there is one.

[Danny Uncanny7]

There are a number of Secret Santa generators available on the internet.

[devgal89]

I did see that topic about secret santas but I felt my conundrum warrented another thread because of its added task of also eliminating previous giftees.

Also I have looked around at many many secret santa generators and none have the option of having restrictions on whether or not the name is draw-able for a certain person.

[Qaanol]

Viewing the adjacency matrix, as a checkboard or spreadsheet, we find that, every year, we must choose a set of N squares such that there is exactly one square in each of the N rows, and exactly one square in each of the N columns, and exactly 0 squares along the main diagonal. And each year all the squares must be different from before.

If you require that all the squares be different from all past years, as long as possible, then on year N-1 you will know (if you have perfect memory) who has whom, because everyone will have the one person they have not yet had. On the other hand, if you just require that all the squares be different from the immediately previous year, you can keep the randomness a lot better.

So the question is then, given an N×N grid, with N cells crossed off, of which exactly one is in each row and one is in each column, and none are on the main diagonal, how can you randomly choose a new, disjoint set of N cells to cross off, following the same restrictions?

[jestingrabbit]

Qaanol, you're forgetting the couples requirement ie no one is paired with their partner.

[mfb]

Why do you treat the different reasons for "X cannot get Y" in a different way?
"we want to make sure we do not get ourselves" -> X cannot get X
"or our spouse/significant other" -> X cannot get Y
"or the one he had last year" -> X cannot get Z

Just cross everything out in the NxN-matrix. Now, the task is just to find a valid solution of one square per row and per column. No special cases involved, diagonals are like any other cells.
Now, a computer can find solutions for that. And I think that random drawing from the possible santas gives good results. Redraw if the algorithm runs into a dead end.
A manual drawing rule might be more difficult.

[Qaanol]

Qaanol, you're forgetting the couples requirement ie no one is paired with their partner.

Yep, you’re right, I missed that. But as mfb says, it’s just a matter of crossing out those extra cells on the adjacency matrix.

[devgal89]

I really do think that an algorithm with a series of if conditionals would be the best solution, and I don't think anyone in the family is married to the concept of physically drawing names. But like I said earlier, I only have had very limited coding experience so doing such a thing I don't believe I'd have the slightest clue on where to even start the formula.

[jestingrabbit]

How big is your family? You're basically searching through about O(n!) possible combinations. At about 10 or 12, that could get pretty slow. At 20, its the sort of thing that you'd have to leave your computer on for, possibly for quite a while. Its also possible, theoretically, that there might be outcomes that prohibit a solution the next year.

Seriously, a bit more thought about when a solution exists could save you a lot of hassles later on, and I figure this isn't time sensitive.

[mfb]

As long as the constraints are not too bad (e.g. "for X, all but two other persons are excluded"), it should be easy to find valid solutions with random searches. As devgal89 said, they had the problem that they had to redraw multiple times - by hand. The computer can exclude persons in advance which speeds up the process, so it should get a valid solution within <100 trials. And even 1 million rounds would be possible within ~1 minute.