Secret Santa Recursive Pairings

pair.php

function make_valid_pairing( $people_to_pair, $people_yet_to_have_gifts ) {

  // We made it! No more people left to pair! Return an empty array of pairings.
  if (empty($people_to_pair)) {
    return [];
  }

  // Get the first person
  $person_to_pair = $people_to_pair[0];
  // Get all the other people
  $other_people_to_pair = array_slice( $people_to_pair, 1 );

  // Get all the possible matches for the person
  $possible_matches = array_diff( $people_yet_to_have_gifts, $person_to_pair->exclusions );
 
  // If there are none we need to bail out somehow - not figured this out yet.
  if (empty($possible_matches)) {
    // not sure what we do here yet
    return something;
  }

  // Randomize the possible matches.
  shuffle( $possible_matches );

  // What we're going to do it try each match in turn. We'll take a match, remove that match from the list
  // of people left to be assigned as giftees, and then try and make a valid pairing of the people that are left
  // by...CALLING THIS FUNCTION ITSELF!!! :-O
  foreach ($possible_matches as $this_match) {

    // Remove this match from the list of people not assigned as giftees
    $remaining_people_yet_to_have_gifts = array_diff($people_yet_to_have_gifts, $this_match);

    // Go and do all the other matches for all the other people yet to be paired. This may be successful, it
    // may not. If we've run out of people, this call will return an empty array that we can add stuff into.
    $other_matches = make_valid_pairing( $other_people_to_pair, $remaining_people_yet_to_have_gifts );

    // If that worked, then add our current pairing to the valid list that we got back and return that new list.
    if ($other_matches is a valid pairing - i.e. there was no error and we didn't run out of people) {
      $other_matches[] = ['gifter' => $person_to_pair, 'giftee' => $this_match];    
      return $other_matches;
    }

    // If we are here then we didn't get a valid pairing of everyone else, so we'll go around the loop and try
    // matching the current person with the next possible match, and then try making a valid list of everyone else again.

}

  // We exited the loop - so we ran out of people to match with and couldn't find a valid pairing of everyone
  return "ERROR"; // Or whatever
}

// Now we have the pairing algorithm we need to start it! Let's give it ALL the members and see what happens.
$paired_members = make_valid_pairing( $members, $members );