title: Secret santa algorithm
body: <p>Every Christmas we draw names for gift exchanges in my family.  This usually involves mulitple redraws until no one has pulled their spouse.  So this year I coded up my own name drawing app that takes in a bunch of names, a bunch of disallowed pairings, and sends off an email to everyone with their chosen giftee.</p>
  
  <p>Right now, the algorithm works like this (in pseudocode):</p>
  
  <pre><code>function DrawNames(list allPeople, map disallowedPairs) returns map
      // Make a list of potential candidates
      foreach person in allPeople
          person.potentialGiftees = People
          person.potentialGiftees.Remove(person)
          foreach pair in disallowedPairs
              if pair.first = person
                 person.Remove(pair.second)
  
      // Loop through everyone and draw names
      while allPeople.count &gt; 0
          currentPerson = allPeople.findPersonWithLeastPotentialGiftees
          giftee = pickRandomPersonFrom(currentPerson.potentialGiftees)
          matches[currentPerson] = giftee
          allPeople.Remove(currentPerson)
          foreach person in allPeople
              person.RemoveIfExists(giftee)
  
      return matches
  </code></pre>
  
  <p>Does anyone who knows more about graph theory know some kind of algorithm that would work better here?  For my purposes, this works, but I'm curious.</p>
  
  <p>EDIT: Since the emails went out a while ago, and I'm just hoping to learn something I'll rephrase this as a graph theory question.  I'm not so interested in the special cases where the exclusions are all pairs (as in spouses not getting each other).  I'm more interested in the cases where there are enough exclusions that finding any solution becomes the hard part.  My algorithm above is just a simple greedy algorithm that I'm not sure would succeed in all cases.</p>
  
  <p>Starting with a complete directed graph and a list of vertex pairs.  For each vertex pair, remove the edge from the first vertex to the second.</p>
  
  <p>The goal is to get a graph where each vertex has one edge coming in, and one edge leaving.</p>