Algorithm for Secret Santa

In my family, we have the tradition of doing Secret Santa for gift exchange, so I wrote a small program that randomly selects pairs of gifters and receivers and then sends an email to each of them informing who they have to give a gift to.

The first iteration of this problem was very convoluted, it tried to use an array of people and randomly select two of them, then it performed a series of checks in order to obey to the game's constraints:

• You can't give a gift to yourself

• You only give one gift

• You can only receive one gift

• You can't give to a person and receive from the same person (not sure if this is actually a rule, but in my mind it is)

This solution is similar to most of other ones I've seen online.

My aha moment

But one day, I got inspired in the shower. I found a bulletproof solution for this problem. I don't really know if this one is out there, but I haven't seen it anywhere else.

It goes like this:

We have an array of gifters (lets make them strings for simplicity). We'll start with the minimum required to apply all the rules: 3

Then we start by shuffling the array. This will provide the randomness we need.

Then we create the receivers array by rotating a copy of the gifters. This is where the magic happens! This step is where we ensure that all of our constraints are met. By performing a rotation, we are sure that we're not giving a present to ourselves, that we're not giving and receiving to and from the same person and that there's only one of each in each array. We could've shuffled, but by doing that, we'd be introducing a high possibility of violating the rules.

Finally, we only need to zip both arrays to get the nth gifter paired with the nth receiver.

  gifters = %w[chris dave matt]
  gifters.shuffle!

  receivers = gifters.dup.rotate

  gifters.zip(receivers) do |gifter, receiver|
    puts "#{gifter} => #{receiver}"
  end

  # >> matt => chris
  # >> chris => dave
  # >> dave => matt

As simple as that!

Here is a shorter and improved version of the exact same algorithm.

First, we assign to the gifters variable the shuffled array and then we zip the rotated version. This is more straight forward and we don't need to introduce a clone of the original array to the mix

  gifters = %w[chris dave matt].shuffle

  gifters.zip(gifters.rotate) do |gifter, receiver|
    puts "#{gifter} => #{receiver}"
  end

  # >> chris => dave
  # >> dave => matt
  # >> matt => chris

Finally, and just to show it off, I'll add more people and perform multiple runs to demonstrate that it works =)

  8.times do |i|
    gifters = %w[john chris dave matt pete jodie].shuffle!

    puts "* Iteration #{i}"
    gifters.zip(gifters.rotate) do |gifter, receiver|
      puts "  #{gifter} => #{receiver}"
    end
    puts "-" * 20
  end

  # >> * Iteration 0
  # >>   jodie => john
  # >>   john => chris
  # >>   chris => pete
  # >>   pete => dave
  # >>   dave => matt
  # >>   matt => jodie
  # >> --------------------
  # >> * Iteration 1
  # >>   john => pete
  # >>   pete => dave
  # >>   dave => matt
  # >>   matt => jodie
  # >>   jodie => chris
  # >>   chris => john
  # >> --------------------
  # >> * Iteration 2
  # >>   john => pete
  # >>   pete => jodie
  # >>   jodie => matt
  # >>   matt => dave
  # >>   dave => chris
  # >>   chris => john
  # >> --------------------
  # >> * Iteration 3
  # >>   john => chris
  # >>   chris => pete
  # >>   pete => matt
  # >>   matt => jodie
  # >>   jodie => dave
  # >>   dave => john
  # >> --------------------
  # >> * Iteration 4
  # >>   jodie => matt
  # >>   matt => pete
  # >>   pete => john
  # >>   john => dave
  # >>   dave => chris
  # >>   chris => jodie
  # >> --------------------
  # >> * Iteration 5
  # >>   matt => chris
  # >>   chris => pete
  # >>   pete => john
  # >>   john => jodie
  # >>   jodie => dave
  # >>   dave => matt
  # >> --------------------
  # >> * Iteration 6
  # >>   john => chris
  # >>   chris => jodie
  # >>   jodie => matt
  # >>   matt => pete
  # >>   pete => dave
  # >>   dave => john
  # >> --------------------
  # >> * Iteration 7
  # >>   pete => matt
  # >>   matt => dave
  # >>   dave => john
  # >>   john => chris
  # >>   chris => jodie
  # >>   jodie => pete
  # >> --------------------

So there you have it, I hope you use it for your next Secret Santa.

Saluti.