An algorithm to generate unbiased pairs of names for a gift exchange or secret santa.
No person can be matched with themselves, anyone in the same group as themselves, or against any of the custom exclusions that can be set.
npm i gift-exchange
gift-exchange exports two functions (
calculateSync) and an
Person array is always required. A
Person must have a unique
Person cannot be matched with another person in the
group nor with themselves. A mix of people that both have and do not
group is supported.
This returns a Promise that resolves with a new array of people or
rejects with a
DerangementError. This error is thrown if the matching
algorithm fails to find a valid match after 1 second, indicating that an
impossible combination of people and exclusions was provided.
This returns a new array of people or throws a
the matching algorithm fails to find a valid match after 1 second, indicating
that an impossible combinations of people and exclusions was provided.
calculateSync functions can also be called with a second
exclusions. This builds upon the concept that no person can match
another in the same group.
There are two exclusion types, one of type
name and one of type
type refers to a key on the
Person interface. The
a selector for any number of people that have the given
type equal to the
value always refers to a
name that the
subject pair cannot match with.
The algorithm is based off of Dr Hannah Dry's solution for secret santa as described in Numberphile video The Problems with Secret Santa. This type of problem is called a derangement. This approach gives each person an equal chance for being matched with any other person. A derangement is made, and then checked for the same group followed by each exclusion in the list of exclusions. If the derangement does not satisfy each exclusion rule, the list of people is shuffled and a new derangement is made.