Algorithm to get all unique pair combinations

Question

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...

Answer 1

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

Answer 2

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 => $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;
}