1
\$\begingroup\$

I am working on making a site which outputs all possible combinations of Secret Santa Pairs. I currently have this working by having the site visitor input the participants and any known couples. Once this is done, the visitor simply clicks the 'Calculate' button and it outputs the unique pairs (minus know couples - because they don't want to be paired), and the unique combinations of unique pairs.

Current Implementation

To achieve this, I have written what I believe to be an efficient algorithm to generate the unique pairs (minus the known couples):

function generateUniquePairs($participants, $known_couples) {
    $participantCount = count($participants);

    $pairs = [];
    $pos = 0;

    for ($i = 0; $i < $participantCount; $i++) {
        for ($j = $i + 1; $j < $participantCount; $j++) {
            $tempPair = [$participants[$i], $participants[$j]];
            if ($known_couples) {

                $isKnowCouple = false;

                foreach($known_couples as $index => $known_couple) {
                    if(($tempPair[0] === $known_couple[0] && $tempPair[1] === $known_couple[1]) || ($tempPair[0] === $known_couple[1] && $tempPair[1] === $known_couple[0])) {
                        $isKnowCouple = true;
                    };
                };

                if ($isKnowCouple === false) {
                    $pairs[$pos++] = $tempPair;
                }
            } else {
                $pairs[$pos++] = $tempPair;
            }
        }
    }

    return $pairs;
}

Which I then pass to a modified (and not efficient) \$\binom{n}{k}\$ algorithm:

$result = array();
$combination = array();

function generateUniqueCombinations(array $unique_pairs, $choose)
{
    global $result, $combination;

    $n = count($unique_pairs);

    function inner($start, $choose_, $arr, $n)
    {
        global $result, $combination;

        if ($choose_ == 0) {
            $combination_count = count($combination);
            $participantCounts = new stdClass();
            $hasDuplicates = false;

            for ($p = 0; $p < $combination_count; $p++) {
                if (!$hasDuplicates) {
                    if (property_exists($participantCounts, $combination[$p][0])) {
                        $hasDuplicates = true;
                    } else {
                        $participantCounts->{$combination[$p][0]} = 1;
                    };

                    if (!$hasDuplicates) {
                        if (property_exists($participantCounts, $combination[$p][1])) {
                            $hasDuplicates = true;
                        } else {
                            $participantCounts->{$combination[$p][1]} = 1;
                        };
                    };
                };
            };

            if (!$hasDuplicates) {
                array_push($result, $combination);
            };

            $hasDuplicates = false;
        } else {
            for ($i = $start; $i <= $n - $choose_; ++$i) {
                array_push($combination, $arr[$i]);
                inner($i + 1, $choose_ - 1, $arr, $n);
                array_pop($combination);
            }
        }
    }
    inner(0, $choose, $unique_pairs, $n);
    return $result;
}

Example Scenario

The following participant list and know couples:

$participants = ["Tom", "Leanne", "Connor", "Sophie", "Tony", "Anita"];
$known_couples = ["Tom", "Leanne"];

$unique_pairs = generateUniquePairs($participants, $known_couples);
$unique_combinations = generateUniqueCombinations($unique_pairs, count($participant) / 2);

should ouput:

// $unique_pairs
[["Tom","Connor"],["Tom","Sophie"],["Tom","Tony"],["Tom","Anita"],["Leanne","Connor"],["Leanne","Sophie"],["Leanne","Tony"],["Leanne","Anita"],["Connor","Sophie"],["Connor","Tony"],["Connor","Anita"],["Sophie","Tony"],["Sophie","Anita"],["Tony","Anita"]]

// $unique_combinations
[[["Tom","Leanne"],["Anita","Tony"]],[["Tom","Anita"],["Leanne","Tony"]],[["Tom","Tony"],["Leanne","Anita"]]]

The Problem

My code works, but if you use a list of participants > 12, it generates an array of unique pairs of length > 66, which means when it gets to running generateUniqueCombinations($unique_pairs, $choose), it times out.

I understand the problem is that my code is doing a lot of throw away processing due to it iterating through hundreds of thousands of potential combinations unnecessarily because those combinations are not viable due to them containing the same person more than once.

Where I need help

I would really like to understand if it is possible to skip past those non-viable combinations mathematically so there is no need to count participants within combinations and unnecessarily iterate.

I really would like my site to be more useful than being able to generate combinations of pairs for only <= 12 participants...

\$\endgroup\$
6
  • \$\begingroup\$ This looks like an XY problem. Is the problem you're really trying to solve finding perfect matchings of an undirected graph? \$\endgroup\$ Oct 14 '17 at 15:11
  • \$\begingroup\$ @PeterTaylor - I have now updated my description to hopefully explain things a bit better! I must confess I am not 100% sure what you mean when you ask if I am 'trying to solve perfect matchings of an undirected graph'. But doing a quick bit of Googling, yes, it does appear I might be trying to achieve that. But maybe you can tell me that for definite with my updated post? \$\endgroup\$
    – Tom Hudson
    Oct 14 '17 at 22:32
  • \$\begingroup\$ Have you looked into PHP's Ds\Set class? It supports operations like set difference and it shouldn't be hard to create an extension that calculates the cartesian product. \$\endgroup\$ Oct 15 '17 at 7:59
  • \$\begingroup\$ @DavidFoerster - I am not sure I want to calculate the Cartesian product in this scenario? Also, why would I use Ds\Set in this scenario? Will using this give a performance boost over using arrays? \$\endgroup\$
    – Tom Hudson
    Oct 15 '17 at 20:45
  • \$\begingroup\$ I am confused by your sample input and the expected output. $known_couples = ["Tom", "Leanne"]; but in the output the first set of pairs is: ["Tom","Leanne"] Can you clarify why that is a valid result? Also, I don't see how you can scale up your $known_couples array with that single-dim structure. Shouldn't the structure be an array of two-element arrays by default? \$\endgroup\$ Oct 16 '17 at 2:11
1
\$\begingroup\$

Firstly, the combination of global variables, an inner function, stdClass, and a lack of comments makes it harder than it should be to understand what the code is doing.

Speed tests carried out with 10 participants and one couple.

Using foreach instead of a simple indexed for in

            for ($p = 0; $p < $combination_count; $p++) {

and eliminating $combination_count reduced the time from about 9.7 secs to 7.9 secs.

Replacing stdClass with a simple array and property_exists with isset reduced it further to 5.3 secs.

And that doesn't yet address the biggest obvious problem:

    function inner($start, $choose_, $arr, $n)
    {
        global $result, $combination;

        if ($choose_ == 0) {
            $combination_count = count($combination);
            $participantCounts = new stdClass();
            $hasDuplicates = false;

            ...

            if (!$hasDuplicates) {
                array_push($result, $combination);
            };

            $hasDuplicates = false;
        } else {
            for ($i = $start; $i <= $n - $choose_; ++$i) {
                array_push($combination, $arr[$i]);

This is where you should be checking for duplicates. Otherwise it will select ["Tom","Connor"] as the first pair, ["Tom","Sophie"] as the second pair, and for each of the (42 choose 3) = 11480 triples chosen from the remaining elements of $unique_pairs it will rerun the duplicate finding code and find that "Tom" is duplicated.


Having said that, I think the best approach would be to start from scratch. The problem you're trying to solve is indeed, as discussed in comments, finding all exact matchings in an almost complete graph. (Or even a complete graph, if there are no couples).

Take a quick sanity check to ask yourself if you really need to find all of them or whether it would suffice to pick one at random. Bear in mind that with \$2n\$ people and no couples the number of exact matchings is \$\frac{(2n)!}{2^n n!}\$. With 18 people that's already 34459425 matchings, so no algorithm which enumerates all of them is going to scale very far.

Whether you decide to generate them all or to randomise and generate one, I would also reconsider the graph structure. $unique_pairs is essentially a list of the edges in the graph, but since it's almost complete it would be more efficient to represent the graph as a list of vertices (people) and a list of edges which aren't in the graph (couples). If you implement the couples as an associative array then testing whether two people form a couple is very fast. The approach would be something like

  • Pick the first person (P) in the list and remove from the list
  • For each other person Q in the list who doesn't form a couple with P:
    • Remove Q from the list
    • Recurse to get partial solutions S
    • Add the pair (P, Q) to each partial solution in S, and append to an accumulator
    • Restore Q to the list
  • Return the accumulator
\$\endgroup\$
1
  • \$\begingroup\$ I have learnt a lot from your answer! I cannot thank you enough. I have implemented your performance suggestions and it has stopped timeouts with larger participant numbers. I can't believe I missed the trick of putting the duplication check before doing all those recursive calls. In addition I have now removed my use of globals, renamed a load of variables, and added comments to my code - sorry about that! For now the performance improvements you suggested are enough, but I will be moving to your suggested accumulator based implementation when I have a bit more time. \$\endgroup\$
    – Tom Hudson
    Oct 16 '17 at 23:27
1
\$\begingroup\$

I feel your code is way more complex then it needs to be. I am guessing in the end you just want to produce a random secret santa list.

I have put some echo statements in the code, so you can easily follow how it works.

This is not the most efficient way of doing this, but I have tried to keep the code as simple as possible.

This list executed in less then 1sec for me, I am pretty sure it would work for at least a few hundred names without timeout

$participants = [
    "Tom", "Leanne",
    "Connor", "Sophie",
    "Tony", "Anita",
    "Sally", "Sam",
    "Joan", "Sarah",
    "Mary", "Thomas",
    "Karl", "Jacob",
    "Jane", "Kelly",
    "Tim", "Marcus",
    "Wayne", "Ronald",
];

$known_couples = [
    "Tom" => "Leanne",
    "Jane" => "Thomas",
];

$pairs = generateList($participants, $known_couples);

var_dump($pairs);



function generateList($participants, $known_couples)
{
    if (count($participants) % 2 !== 0) {
        die("Sorry, only works for an even number of participants");
    }

    $participants1 = $participants;
    shuffle($participants1);

    $participants2 = $participants;
    shuffle($participants2);

    $pairs = [];
    $unique_pairs = [];

    foreach($participants1 as $participant1) {

        foreach($participants2 as $participant2) {

            echo "$participant1 =&gt; $participant2 ";

            if (isset($pairs[$participant1])) {
                // to improve performance you can perform this test within the previous foreach loop
                echo " -- Skip, {$participant1} already has a secret santa<br>";
                continue;
            }

            if (isset($pairs[$participant2])) {
                echo " -- Skip, {$participant2} already has a secret santa<br>";
                continue;
            }

            // can't have a person giving to themselves
            if ($participant1 == $participant2) {
                echo " -- Skip, same person<br>";
                continue;
            }

            // do the most expensive test last
            if (isKnownCouple($participant1, $participant2, $known_couples)) {  
                echo " -- Skip, known couple<br>";
                continue;
            }


            $pairs[$participant1] = $participant2;
            $pairs[$participant2] = $participant1;

            $unique_pairs[$participant1] = $participant2;

            // performance improvement, once match is found, break out of the foreach
            echo " ** MATACH<br>";
        }
    }

    return $unique_pairs;
}


function isKnownCouple($participant1, $participant2, $known_couples)
{
    // performance improvement build an array at the start 
    // couple 1, couple 2, couple 2, couple 1, then just check if array key exists isset($couples[couple 1][couple 2])
    foreach ($known_couples as $known_couple_1 => $known_couple_2) {

        if ($participant1 == $known_couple_1 && $participant2 == $known_couple_2) {
            return true;
        }

        if ($participant1 == $known_couple_2 && $participant2 == $known_couple_1) {
            return true;
        }
    }

    return false;
}
\$\endgroup\$
1
  • \$\begingroup\$ Although I do appreciate your efforts. This doesn't achieve what I want. My code works as is, it's just inefficient. Your code gives a totally different output. However, I forgot it's possible to use continue within a loop in PHP, so a lot of my code to set hasDuplicates or isKnownCouple can be removed and replaced with a continue. This would give a performance boost in those "throw away" iterations but the goal here is not to do that iteration in the first place. \$\endgroup\$
    – Tom Hudson
    Oct 15 '17 at 6:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.