2

There is an array with names, for example:

$donalds_nephews = array('Huey', 'Dewey', 'Louie');

array
(
    [0] => Huey
    [1] => Dewey
    [2] => Louie
)

I want to shuffle this array, but ensure that no value of the original array has the same key as the shuffled one.

$donalds_nephews_shuffled = shuffle($donalds_nephews);

This could result in 6 possible permutations:

  1. Huey, Dewey, Louie
  2. Huey, Louie, Dewey
  3. Dewey, Louie, Huey
  4. Dewey, Huey, Louie
  5. Louie, Dewey, Huey
  6. Louie, Huey, Dewey

1st, 2nd, 4th and 5th must not be the result.

What's the best way to do so? It's for Secret Santa.

user229044
  • 232,980
  • 40
  • 330
  • 338
Ben
  • 1,550
  • 1
  • 16
  • 24

5 Answers5

5

Shuffle the original array, then make a copy of it and shift all entries one over, then match the two back together to get your matches.

deceze
  • 510,633
  • 85
  • 743
  • 889
  • That sounds clever. What would be the best way to shift all values one over? – Ben Dec 12 '12 at 22:42
  • 1
    @Ben `$array[] = array_shift($array);` – deceze Dec 12 '12 at 22:57
  • Oh, great. I was thinking of a for loop. Is `$array = array_shift($array);` wihout brackets also okay? – Ben Dec 13 '12 at 15:47
  • 1
    @Ben No, that's not the same thing. – deceze Dec 13 '12 at 15:47
  • Additionally, what, if I have a list of 2-tuples containing names of persons, who should not be Secret Santa partners, because they dislike each other? That makes it complicated, doesn't it? – Ben Dec 13 '12 at 15:50
  • 1
    Yeah, that makes it pretty complicated. Then you pretty much have to loop through all names, prepare an array of possible candidates for each name which does not include himself or people he dislikes, choose a random one, remove the choice from the global pool and repeat. That of course may get you into a deadlock where some don't get any partner. – deceze Dec 13 '12 at 15:52
  • Thank you very much for your fast answer. To avoid a deadlock was actually my problem while trying. – Ben Dec 13 '12 at 15:55
  • Do you have any idea how to avoid a deadlock? – Ben Dec 13 '12 at 16:14
  • 1
    @Ben Nope. Seems like a nice involved mathematical problem. No idea if there's even a solution to it. I'd try a new question, possibly even on one of the more theoretical/mathematical sites. – deceze Dec 13 '12 at 16:17
  • Last question: how would you match the two arrays back together? – Ben Dec 13 '12 at 16:33
  • @Ben Depends on what the result should look like. `array_combine($array1, $array2)` or `array_map(null, $array1, $array2)` would be my guess. – deceze Dec 13 '12 at 16:51
1

It's for Secret Santa.

Then start with a better algorithm. Currently you seem to be inferring that the key is a present giver and the value a present receiver (or vice versa). This then entails the additional check (and possible re-iteration of the shuffling) to ensure that nobody ends up giving a present to themselves.

But what if you just consider it as an ordered list of names, such that each entry gives to the next person on the list:

$victims=array('Huey', 'Dewey', 'Louie');
shuffle($victims);
$giver='';
foreach($victims as $receiver) {
  if ($giver) print "$giver gives to $receiver\n";
  $giver=$receiver;
}
$receiver=array_shift($victims);
print "$giver gives to $receiver\n";
symcbean
  • 47,736
  • 6
  • 59
  • 94
1

just cause i need this for my secret santa :) 

<?php

    function compareArrays($original, $shuffled){   
        for($i = 0; $i < count($original); $i++ ){
            if($original[$i] == $shuffled[$i]){
                return false;
            }
        }
        return true;
    }

    $donalds_nephews = array('Huey', 'Dewey', 'Louie','Igor','Stephan');

    //avoid loops
    for($j = 0; $j < 50; $j++){
        $shuffled = $donalds_nephews;
        shuffle($shuffled);
        $good = compareArrays($donalds_nephews, $shuffled);

        if($good) break;
    }

    if($good){
        echo "here we go!\n";
        foreach($shuffled as $k => $v){
            echo "$k => $v \n";
        }
    }
    else { 
        echo "try again \n";
    }

?>
Gianpaolo Di Nino
  • 1,139
  • 5
  • 17
0

Don't make this complicated by trying to put all of this into one function.

Here's your pseudocode:

$givers  = array( 'Huey', 'Dewey', 'Louie' );
$getters = $givers;

foreach ( $givers as $giver ) {
    do {
        pick a random $getter from $getters;
    } until $getter <> $giver;
    delete $getter from $getters;
    print "$giver gives to $getter\n";
}
Andy Lester
  • 91,102
  • 13
  • 100
  • 152
  • That's a very non-deterministic algorithm and may possibly never finish in the worst case scenario. – deceze Dec 12 '12 at 22:34
0

It is an old question, but you asked for the best way, so how about this?

function santaYates($array) {
    $returnArray = array_values($array); // Cause we need a clean numeric array
    $secure = false;
    for($i = count($returnArray) - 1; $i > 0; $i--) {
        $r = mt_rand(0, $i-1); //subtract 1 from $i to force a new place.
        $tmp = $returnArray[$i];
        $returnArray[$i] = $returnArray[$r];
        $returnArray[$r] = $tmp;
    }

    return $returnArray;
}

It works very similar to the Fisher-Yates shuffle.

There is just one little difference: We permit to use the same key, so every entry will get a new place (cause we substract 1 from $i when we do the randomize step).

Working Demo

A.F.
  • 41
  • 7