which algorithm php to create a secret Santa program-CodePudding

I'm trying to make a draw for a secret Santa. I collect in a table the information of the person and the name of the person on whom it should not fall (to avoid couples). However during my PHP loop I can't take into account my exclusions

foreach ($supplier as $sup){
    $exclude = $sup['blacklist'];
    $data = $recipient;
    $temp = array_diff($data[], array($exclude));
    echo $temp[rand(0, sizeOf($temp))];

    foreach ($recipient as $key=>$recip){
        if ($sup['surname'] !== $recip['surname']){
            $result[] = ['recipient' => $recip, 'supplier' => $sup];
            unset($recipient[$key]);
        }
    }
}

How can I take into account this blacklist please?

CodePudding user response：

        shuffle($supplier);
        shuffle($recipient);
        //        dump($supplier, $recipient);

        $result = [];

        foreach ($supplier as $sup){
            $assign = false;
            dump($sup);
            foreach ($recipient as $key=>$recip){
                dump($recip['surname']);
                if ($sup['surname'] !== $recip['surname'] && $sup['blacklist'] !== $recip['surname'] && $sup['surname'] !== $recip['blacklist']){
                    $result[] = ['recipient' => $recip, 'supplier' => $sup];
                    dump($sup['surname']);
                    unset($recipient[$key]);
                    $assign = true;
                }
                if ($assign === true){
                    break;
                }
            }
        }
        return $result;
    }

this is my code with shuffle

CodePudding user response：

Your solution is fine, but with that nested loop it's going to start behaving poorly as the list of participants grows. You can accomplish the task with a single array and two linear passes over it:

$people = [
    [ 'name' => 'alice', 'blacklist' => ['bob'] ],
    [ 'name' => 'bob', 'blacklist' => ['alice'] ],
    [ 'name' => 'carl', 'blacklist' => ['david'] ],
    [ 'name' => 'david', 'blacklist' => ['carl'] ],
    [ 'name' => 'elise', 'blacklist' => ['frank'] ],
    [ 'name' => 'frank', 'blacklist' => ['elise'] ],
    [ 'name' => 'georg', 'blacklist' => ['herb'] ],
    [ 'name' => 'herb', 'blacklist' => ['george'] ]
];

function wrap_index($count, $index) {
    $cur  = $index;
    if( $index == 0 ) {
        $prev = $count - 1;
        $next = $index   1;
    } else if( $index == $count - 1) {
        $prev = $index - 1;
        $next = 0;
    } else {
        $prev = $index - 1;
        $next = $index   1;
    }
    return [$prev, $cur, $next];
}

function array_swap(&$array, $a, $b) {
    $tmp = $array[$a];
    $array[$a] = $array[$b];
    $array[$b] = $tmp;
}

function santify($people) {
    shuffle($people);
    
    $count = count($people);
    for( $i=0; $i<$count;   $i ) {
        list($prev, $cur, $next) = wrap_index($count, $i);
        if( in_array($people[$cur]['name'], $people[$next]['blacklist']) ) {
            printf("%s in blacklist for %s\n", $people[$cur]['name'], $people[$next]['name']);
            array_swap($people, $cur, $prev);
        }
    }
    
    $pairs = [];
    for( $i=0; $i<$count;   $i ) {
        list($prev, $cur, $next) = wrap_index($count, $i);
        $pairs[] = [ $people[$cur]['name'], $people[$next]['name'] ];
    }
    
    return $pairs;
}

foreach( santify($people) as $pair ) {
    printf("%s\n", json_encode($pair));
}

Output:

david in blacklist for carl
elise in blacklist for frank
["david","georg"]
["georg","carl"]
["carl","bob"]
["bob","herb"]
["herb","elise"]
["elise","alice"]
["alice","frank"]
["frank","david"]

There is a caveat to this approach, though. It will only work with strict 1:1 blacklist arrangements. Once there is a love triangle [or quardrangle or above] or any polyamory, neither of our solutions is equipped for these extra dimensions.