0

I'm building a gift exchange website, where people put in their emails, and then each of the entrants is matched with another entrant (the sender). I'm using PHP (probably Symfony, if it makes a difference).

I'm expecting the number of entrants to be around 600-800, and this will be run quite frequently.

I thought I could use shuffle() and array_combine() on the array of recipients to do this. However, after the shuffle() the sender could still be in the same position, so would have to give a Secret Santa present to themselves.

For example:

$recipients = "SQL query that returns array"
# ['bob', 'alice', 'joe']

$senders = $recipients; 
shuffle($senders);
# ['alice', 'bob', 'joe']

$result = array_combine($recipients, $senders);
# ['bob' => 'alice', 'alice' = 'bob', 'joe' => 'joe']

So I need to guarantee that in the final array, none of the values equal the key. So far, I have thought of the following possible solutions but they all seem expensive and a bit rubbish:

  1. Use array_walk() over the final array. Put any values into another array, then swap them with each other afterwards. If there's only 1, just swap it with anything.
  2. Take all the values from the $recipients array that have even keys, and all the values from the $senders array that have odd keys. Shuffle both of those arrays.
  3. Instead of using shuffle() implement my own crappy version that does something like shift all the values forward two, and then do array_reverse().
  4. Loop through recipients, and use array_rand() to pick an item from $senders. If it's the same, pick again, otherwise remove it from the array, set it the be the sender for that recipient, and move on to the next recipient.

Perhaps I'm overthinking this - is there a simpler way? Or is there a special way of doing this in PHP that I don't know about?

Dan Blows
  • 20,846
  • 10
  • 65
  • 96
  • possible duplicate of [PHP - Make an associative array unique, key -> value and value -> key](http://stackoverflow.com/questions/15040084/php-make-an-associative-array-unique-key-value-and-value-key) –  Aug 06 '14 at 21:51
  • @Dagon that question is asking about removing duplicate key-value pairs from an associative array. In this question, I'm not trying to remove duplicates, I'm trying to prevent `shuffle()` producing an array where the key equals the value. – Dan Blows Aug 06 '14 at 21:58

2 Answers2

5
  1. shuffle
  2. create a copy
  3. perform a circular shift

  4. combine 

    $users = array('bob', 'alice', 'joe');

shuffle($users);

$santas = $users;
$santas[] = array_shift($santas);

$result = array_combine($santas, $users);

var_dump($result);

Demo: http://codepad.org/jxrzczRG

zerkms
  • 249,484
  • 69
  • 436
  • 539
  • What do you mean by a circular shift? – Dan Blows Aug 06 '14 at 21:50
  • @Blowski Imagine your array as a rolling disk, so when you move your array one position forward, the last element takes the first position, the first element takes the second position, so on and so forth. – ILikeTacos Aug 06 '14 at 21:51
  • Oh just read, I think I understand. `shuffle()` the array, and then do a simple version of solution #3 – Dan Blows Aug 06 '14 at 21:51
  • @zerkms been thinking about this, and there's still no guarantee that in the resulting array, no user will equal the relevant santa. They could be in different positions before the circular shift, and then in the same position after. – Dan Blows Aug 07 '14 at 06:38
  • @Blowski: there is guarantee for that. As soon as there are more than 2 people in total - after a circular shift they will **ALWAYS** be different. If you still think I'm wrong - try to provide the *shuffled `$users`* array that proves your point. – zerkms Aug 07 '14 at 08:31
  • @zerkms Sorry, I didn't actually do the code and I realise now that you're right. – Dan Blows Aug 12 '14 at 12:14
0

You could also use a similar code to the Fisher-Yates shuffle.

function santaYates($array) {
    $keys = array_keys($array); //Store the keys
    $values = array_values($array); // Cause we need a clean numeric array for this kind of randomisation
    $secure = false;
    for($i = count($values) - 1; $i > 0; $i--) {
        $r = mt_rand(0, $i-1); //subtract 1 from $i to force a new place.
        $tmp = $values[$i];
        $values[$i] = $values[$r];
        $values[$r] = $tmp;
    }
    $returnArray = array_combine($keys, $values); //Now recombine keys and values
    return $returnArray;
}

I wrote this code for answering a similar question but this version can also handle associative arrays. You can Test this version

A.F.
  • 41
  • 7