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.
Appendix
I was asked to create a table for a family of six pairs. Please realize that a random exchange allows people to repeat giving, such as P1 giving to P4 multiple times in the following table. If you don't want to give to Uncle Mortimer yet again, switch with your spouse or another family member for that one year, or use a round-robin strategy, which is not random but eliminates duplicates.
11 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.
Thank you for the spring board! This allows everyone to gift everyone else with only a single repeat person due to the single person needing to gift everyone. If I’m not mistaken there are no giver/receiver gift swaps and you can get through it in 6 years.
P1 Sp1 P2 Sp 2 P3 Sp3 P4
——————————————————
Yr 1 Sp3 P4 Sp1 P3 P1 P2 Sp 2
Yr 2 P3 Sp3 P4 P1 Sp 2 Sp1 P2
Yr 3 Sp 2 P2 P3 Sp3 Sp1 P4 P1
Yr 4 P4 P3 P1 Sp1 P2 Sp 2 Sp3
Yr 5 P2 Sp 2 Sp3 P3 P4 P1 Sp1
Yr 6 Sp 2 Sp3 P1 P4 Sp1 P2 P3
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?
I keep getting an error when I got the link to download. Can you do one for a family of 12 please! It’s been very frustrating having the family do the random name generator, everyone keeps getting the same person over and over. I have had the same person 3 times in the last 5 years lol
OK. See the appendix.