One aspect of blogging that I enjoy is getting feedback from readers. Usually I get statistical or programming questions, but every so often I receive a comment from someone who stumbled across a blog post by way of an internet search. This morning I received the following delightful comment on my 2010 post, "Automating the Great Christmas Gift Exchange":
This is exactly what I need!!! We are a family of 10, including parents, siblings, and siblings' spouses. Spouses don't give to each other and of course you don't give to yourself! For the life of me, I can't figure out how to do it. I'm NOT a statistical programmer and need help! I'll send you some cookies this Christmas if you can create my family's gift exchange grid!!
Debbie
So, at Debbie's request, I will revisit the Great Christmas Gift Exchange.
See the original article for the details, but the main idea is to define a feasible matrix: an N x N matrix of zeros and ones, where N is the number of people participating. In Debbie's case, N=10. The matrix has a 1 in the (i,j) position if person i is permitted to give to person j. In Debbie's case, the matrix is all ones except for 2x2 blocks of zeros along the diagonal:
proc iml;
/* algorithm to generate random gift exchange */
/* Person_1 Spouse_1 ... Person_5 Spouse_5 */
names = {P1 Sp1 P2 Sp2 P3 Sp3 P4 Sp4 P5 Sp5};
N = 10;
Valid = {0 0 1 1 1 1 1 1 1 1,
0 0 1 1 1 1 1 1 1 1,
1 1 0 0 1 1 1 1 1 1,
1 1 0 0 1 1 1 1 1 1,
1 1 1 1 0 0 1 1 1 1,
1 1 1 1 0 0 1 1 1 1,
1 1 1 1 1 1 0 0 1 1,
1 1 1 1 1 1 0 0 1 1,
1 1 1 1 1 1 1 1 0 0,
1 1 1 1 1 1 1 1 0 0
}; |
One way to generate gift exchanges is to generate random permutations. If the permutation is feasible (which you can determine by comparing it with the feasible matrix), then keep the permutation, otherwise generate another random permutation. This is implemented in the following program (download the program):
/* helper module: create a permutation matrix from a permutation, v */
start GetPermutationMatrix(v);
n = ncol(v);
P = j(n, n, 0);
do i = 1 to n;
P[i, v[i]] = 1;
end;
return (P);
finish;
NumYears = 10;
v = j(NumYears, N, .); /* to store valid permutations */
/* create random permutation of 1:N */
call randseed(12252011); /* set random seed; I used 12/25/2011 */
do Year = 1 to NumYears;
s = 0;
do while(s<N);
perm = ranperm( N );
P = GetPermutationMatrix( perm );
s = sum(Valid#P); /** check if permutation is valid **/
end;
v[Year, ] = perm; /* got a valid gift exchange; save it */
end;
years = char(1:N);
Exchange = shape( names[v], N );
print Exchange[r=years c=names]; |
The above matrix gives valid gift exchanges for the next ten years for Debbie's family. Each column is a name; each row is a year. The names (column headers) stand for "Person" and "Spouse." Debbie might assign P1=Dad, Sp1=Mom, P2=Brother1, Sp1=Sister-in-law1, ..., P5=Debbie, Sp5=Husband. For Year 1, Dad give to P3, Mom gives to Husband, Brother1 gives to Debbie, Sister-in-law1 gives to Dad, ..., Debbie gives to Brother1, and Husband gives to Sister-in-Law1.
So that I don't get overwhelmed with cookie offers, here are possible ways to exchange gifts if your family has eight people (four pairs of spouses), six people (three pairs of spouses), or four people (two pairs of spouses). Notice that for two pairs of spouses, there are only four possible arrangements. You can also use an alternative algorithm for the case of three pairs of spouses, as shown at the end of my previous blog post.
As for the cookies, Debbie, this one's on me. If you feel compelled to show appreciation, please bring your home-baked cookies to a homeless shelter in your community or donate canned goods to a local food pantry.
8 Comments
OK, I feel kind of silly, but I have to admit that I had never thought of this. The good thing is that it can work for even a medium-sized family, like mine, which has three brothers and their spouses. It is especially helpful in the tough economy where some of us would struggle to buy for everyone. Plus, it's better than the old "drawing names" deal.
Pingback: This week in blogs: abbreviations, innovation and the holidays - SAS Voices
Excellent post! I have been looking for a way to set this up for my family so there was no gifting overlap through the years. We have an additional requirement though: for our 6-person family, we wanted the additional restriction that there is no reciprocal gift-giving in a given year: i.e. if person A is giving to person B, person B can't be giving to person A. I couldn't figure out how to integrate this requirement into the program; anyone have any ideas?
Great idea.... but what if one of the family members is single. My situation - 3 couples and 1 single person. is that a simple fix?
Gift Exchange: 4 Pairs of Spouses + 1 Extra P1 SP1 P2 SP2 P3 SP3 P4 ---------------------------------- Year 1 SP3 P3 P4 P1 SP2 SP1 P2 Year 2 P3 P4 SP1 P1 SP2 P2 SP3 Year 3 SP3 P2 SP1 P3 P4 P1 SP2 Year 4 SP2 P2 P3 SP3 P1 P4 SP1 Year 5 SP3 P2 P4 P3 P1 SP2 SP1 Year 6 P3 P2 P1 SP3 P4 SP2 SP1 Year 7 SP3 P4 P3 SP1 P1 SP2 P2 Year 8 P3 P2 SP3 P4 SP2 SP1 P1 Year 9 P3 P2 P1 SP3 P4 SP1 SP2 Year 10 SP2 P3 P4 SP3 P2 SP1 P1This doesn't work at all P1 is giving to SP3 almost every other year, along with every other person repeats are all over the place.
That's randomness. When you flip a coin, you don't get an alternating sequence of heads and tails. Sometimes you get two, three, or even four heads in a row. If you don't want randomness, use a round-robin sequence where P1 alternately gives to each family member and the sequence repeats itself every few years.
I love that I found this on the inter webs. Thank you!
I created a round-robin spreadsheet for 8 gift-givers giving to each other. One of the years ends up being a "giving to yourself year" so we just skip that one. But there's another year where it turns into a reciprocal gift swap (person A gives to person B, person B gives to person A), which we'd like to skip as well. But I can't figure out how to do it. Simply skipping that year means those gifters never give to each other. Can anyone think of a way to systematize it so there is no reciprocal gift swap? Or even a non-systematized way that makes it work?