The great Christmas gift exchange revisited

7

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.

Share

About Author

Rick Wicklin

Distinguished Researcher in Computational Statistics

Rick Wicklin, PhD, is a distinguished researcher in computational statistics at SAS and is a principal developer of PROC IML and SAS/IML Studio. His areas of expertise include computational statistics, simulation, statistical graphics, and modern methods in statistical data analysis. Rick is author of the books Statistical Programming with SAS/IML Software and Simulating Data with SAS.

7 Comments

  1. 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.

  2. Pingback: This week in blogs: abbreviations, innovation and the holidays - SAS Voices

  3. 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?

  4. 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?

    • Rick Wicklin
      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  P1
      • This 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.

        • Rick Wicklin

          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.

Leave A Reply

Back to Top