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 150200 on one person is cheaper and easier than spending 3550 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 redraw. This year we did four redraws 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 goaround. 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?
My Family's Secret Santa
Moderators: jestingrabbit, Moderators General, Prelates
Re: My Family's Secret Santa
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 nonrepetition 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 santarecipient 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 santarecipient 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.
This time you want nonrepetition 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 santarecipient 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 santarecipient 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.
wee free kings

 Posts: 74
 Joined: Wed Oct 12, 2011 12:53 pm UTC
Re: My Family's Secret Santa
There are a number of Secret Santa generators available on the internet.
Re: My Family's Secret Santa
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 drawable for a certain person.
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 drawable for a certain person.
Re: My Family's Secret Santa
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 N1 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?
If you require that all the squares be different from all past years, as long as possible, then on year N1 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?
wee free kings
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5959
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: My Family's Secret Santa
Qaanol, you're forgetting the couples requirement ie no one is paired with their partner.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Re: My Family's Secret Santa
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 NxNmatrix. 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.
"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 NxNmatrix. 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.
Re: My Family's Secret Santa
jestingrabbit wrote: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.
wee free kings
Re: My Family's Secret Santa
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
 Factoids are just Datas that haven't grown up yet
 Posts: 5959
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: My Family's Secret Santa
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.
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.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Re: My Family's Secret Santa
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.
Who is online
Users browsing this forum: Sandor and 4 guests