A Ruby implementation of derangement (secret santa) algorithm

Question

A secret santa gift exchange is a game where each player is randomly assigned a person to whom they anonymously give a gift. The algorithm is referred to as Derangement.

For example, given the following players:

Mohamad, Carolina, Sami, Tania, Ikram, José

A game may be:

Mohamad gets Sami
Carolina gets José
Sami gets Tania
Tania gets Mohamad
Ikram gets Carolina
José gets Ikram

The important rules are:

1. A person can not be assigned to themselves.
2. A person can only be assigned to another person once.
3. Assignment must be random.

Implementation

This is my object oriented implementation. I do not like my random_player_for implementation. It seems procedural and the use of temporary flags seems like a code smell.

How would you improve this implementation?

class Derangement
  attr_reader :game

  # for convenience
  # PLAYERS = %w[Mohamad Carolina Sami Tania Jose Ikram Rabii Ahmad Kazem]

  def initialize(players)
    @players = players
    @santas = players.dup
    @game = {}
  end

  def solve
    @santas.each do |santa|
      @game[santa] = random_player_for(santa)
    end
  end

private

  def random_player_for(santa)
    found = false
    until found do
      player = @players.sample
      unless player == santa
        found = true
        @players.delete(player)
      end
    end
    player
  end
end

Answer 1

I'm a bit unsure about whether the question is about a game of Secret Santa or if it's actually about derangement, specifically. Derangement requires that no element can appear in its original position. But that's irrelevant for a game of Secret Santa, since there's no ordering to speak of.

Edit: As tokland rightly points out in the comments derangement is of course related to the game. I wasn't thinking it through.

For derangement, Rosetta Code has a Ruby implementation you might be able to use or learn from.

For a game of Secret Santa, though, the specs are pretty much as you summed up in your 3 rules (although #3 "Assignment must be random" is a bit difficult to define/verify.) So here, things can be simplified; you need not worry about derangement "by itself" as long as the rules are obeyed. For instance, you might simply do:

players = %w[Mohamad Carolina Sami Tania Ikram Jose].shuffle
players << players.first # repeat the first player

assignments = players.each_cons(2).to_a

which will give you an array of santa/gift-receiver pairs such as:

[["Carolina", "Ikram"],
 ["Ikram", "Mohamad"],
 ["Mohamad", "Jose"],
 ["Jose", "Tania"],
 ["Tania", "Sami"],
 ["Sami", "Carolina"]]

Alternatively, you can get the "Santa targets" for several rounds by doing something like

players = %w[Mohamad Carolina Sami Tania Ikram Jose].shuffle
assignments = players.each_with_index.map do |santa, index|
  others = players.rotate(index+1)[0...-1]
  [santa, others]
end

Which will give you something like

[["Tania", ["Mohamad", "Sami", "Ikram", "Carolina", "Jose"]],
 ["Mohamad", ["Sami", "Ikram", "Carolina", "Jose", "Tania"]],
 ["Sami", ["Ikram", "Carolina", "Jose", "Tania", "Mohamad"]],
 ["Ikram", ["Carolina", "Jose", "Tania", "Mohamad", "Sami"]],
 ["Carolina", ["Jose", "Tania", "Mohamad", "Sami", "Ikram"]],
 ["Jose", ["Tania", "Mohamad", "Sami", "Ikram", "Carolina"]]]

There's a pattern of course (if you've given Ikram a gift, next you'll be giving Carolina a gift, then José, etc.). But if it's Secret Santa, the players shouldn't be able to figure that out anyway unless they cheat (and if they do, well, all bets are off).

You could of course use Array#combination or Array#permutation to achieve similar results. I highly encourage you to check out all of the built-in array methods, and those included from the Enumerable module. There's a lot of good stuff there.

As for a more OOP approach, I wouldn't make a class called "Derangement". Derangement is a method. It's an action, an operation, a means of achieving a certain result or state - not something that is itself stateful.
The simple solution, given your code, is to rename you class to "Game" or something along those lines.

Answer 2

Your random_player_for() method can be better expressed as:

  def random_player_for(santa)
    loop do
      player = @players.sample
      if player != santa
        @players.delete(player)
        return player
      end
    end
  end

However, you should recognize that there is a possibility for an infinite loop, if all other players have already been assigned to each other and there is only one loner left.

The following method would be an improvement in two ways:

• Predictable running time
• Detection of a loner

  def random_player_for(players, santa)
    others = players.reject { |player| player == santa }
    if others.empty?
      throw LonerException.new(santa)
    else
      return players.delete(others.sample)
    end
  end

Then, if solve() catches the LonerException, it could retry all the assignments from scratch.

  def solve
    begin
      @game = {}
      players = @players.dup
      @santas.each { |santa| @game[santa] = random_player_for(players, santa) }
    rescue LonerException
      retry
    end
  end

Better yet, modify random_player_for() such that when there are only two players left, and at least one of them has not yet been given an assignment as a Santa, take care to assign them in such a way that there is no loner.