11月 152011
 

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.

tags: Just for Fun, Sampling and Simulation

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)