Random pairing with exclusions

[Hani79]

I'm trying to figure out the most efficient way of pairing two arrays with exclusions.  I don't know if there is a way to do it without walking the array and pairing elements randomly (taking into account the exclusions) and hoping the last pair meets the exclusion requirements.  (And if it doesn't, start the random pairing over.)  Honestly, it doesn't sound like that is the best way to achieve the goal, but I don't know...

 

Here is the "real world" scenario:

 

I'm trying to write a script that selects recipients in a Secret Santa drawing.  There will be exclusions set so that spouses cannot wind up "drawing" each others names - among other specific, user-set exclusions.

 

I am aiming to make the random pairing foolproof and "predictable".  Simply put, if there is NO WAY for the pairings to be valid, I'd like the script to know that before it attempts to pair it up in a loop until it is valid.  Obviously, I'd like to avoid the script trying to pair up two arrays when it is impossible.  I'd like it to warn the user that their current exclusion setup has resulted in an impossible scenario before it even starts the random pairing.

 

Any tips would be great and MUCH appreciated!

[iversonm]

What do you have so far?

Are you going to be storing the people in database?

[Hani79]

I actually didn't start coding before I posted my question.  I wanted to first figure out if the target functionality is even possible.  (Which is: to know if the random pairing process is possible given the exclusions before pairing is even started.)  However, for the sake of showing I actually gave this some thought, I'll show you what I had in mind, and the dilemma that results.

 

(Ultimately, yes, names, exclusions and pairings will be stored in a MySQL database.  Each person will have a one-to-many relationship with the exclusions and a one-to-one relationship with the person they are paired with.  My example below will have hard-coded arrays to emulate the information in the database.)

 

<?php

function doMatching($people,$exclusions) {

  $pairings = array(); // create empty array for the pairings

  foreach ($people as $giverID => $giverName) { // loop through people

    $recipients = $people; // array of potential recipients, not taking account any exclusions
    unset($recipients[$giverID]); // giver cannot be the same as the receiver, remove them from the array
    
    if ( array_key_exists($giverName,$exclusions) ) { // if this person has any exclusions defined
      foreach ($exclusions[$giverName] as $key => $excludedID) { // loop through exclusions and...
        unset($recipients[$excludedID]); // ...remove any person excluded from recieving a gift from this giver
      }
    }
    
    foreach ($pairings as $theGiverID => $theReceiverID) {
      unset ($recipients[$theReceiverID]); // remove any person already randomly selected as a recepient.  (Has no effect during first pass through the loop.)
    }
    
    if (count($recipients) > 0) { //if there are any possible recipients left in the recipients array
      $pairings[$giverID] = array_rand($recipients, 1); // randomly select a recepient from the remaining possible people for this giver
    } else {
      return die('The pairing failed');
    }
  }
  
  return ($pairings);

}

$people = array(0=>'Bob',1=>'Sally',2=>'Timothy',3=>'Jill'); // manually defined keys to emulate id field in database table

$exclusions = array( // We'll use names for the array key in this example to make it easier to read
  'Bob'=>array(1,2),
  'Sally'=>array(0),
  'Timothy'=>array(1),
  'Jill'=>array(0)
);

$pairings = doMatching($people, $exclusions);

print_r($pairings);

?>

 

Given the exclusions in the example above, there is only one valid way of pairing up everyone - and it results in the following pairs (based on the IDs of each person):

Array ( [0] => 3 [1] => 2 [2] => 0 [3] => 1 ) 

 

Let's change the people but keep the exclusions the same in the above code to:

 

$people = array(0=>'Bob',1=>'Sally',2=>'Timothy',3=>'Jill',4=>'Matthew',5=>'Becky',6=>'Peter',7=>'Betty');

 

Given this expanded set of people and the same exclusions, there are a number of ways to pair up givers and recipients.  However, every now and then when you run the code, the pairings will fail if the pairing process "gets off on the wrong foot" and this is expected given that exclusions exist.

 

We can force the pairing to fail if we go back to the original people, but add one more exclusion (Jill cannot get Sally as her receiver.):

 

$people = array(0=>'Bob',1=>'Sally',2=>'Timothy',3=>'Jill');

$exclusions = array(
  'Bob'=>array(1,2),
  'Sally'=>array(0),
  'Timothy'=>array(1),
  'Jill'=>array(0,1)
);

 

Now that we've gone through the examples that either have only one possible pairing scenario (which will always work given the exclusions and their order), have multiple pairing scenarios, or have no pairing scenarios, the major dilemma can be illustrated.

 

If the pairing fails, either there is no valid pairing scenario at all or the script simply "got off on the wrong foot", as may happen in the second example.  Given the possibility that there IS a solution, the script should loop through again and have another attempt at pairing the individuals.  So then, how many times should the script attempt the pairing (after it fails) until the script says, "Enough is enough. There is no solution."?  There really is no definitive answer - it can go on forever (or until the script times out).  The only foolproof way of doing this is by figuring out before the pairing process beings is if there even IS a pairing solution.

 

With all that said, I suppose this is a mathematical question (maybe?).  Is it possible to know if there is at least one solution before even attempting the pairing process?