A Ruby implementation of derangement (secret santa) algorithm

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:

Carolina gets José
Sami gets Tania
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

# 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


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


[["Carolina", "Ikram"],
["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.

• @Flambino: AFAICS the Secret Santa game is 100% related to derangement, since persons.zip(persons.shuffle_with_derangement) is the solution to the problem. Mar 24, 2014 at 10:50
• @tokland Ah, you're right, of course. I'll update my answer - thanks! Mar 24, 2014 at 11:01
• @tokland I don't understand something. Is shuffle_with_derangement a ruby method? I can't find it in the docs. Mar 24, 2014 at 11:52
• @Mohamad No, you must write Array#shuffle_with_derangement yourself :) It was just an example to show the relation (but you can actually implement it this way). Mar 24, 2014 at 11:59
• @Mohamad: Ruby has a Array#shuffle method, but of course it does not enforce that all elements end up in different positions as you need. But I think this is correct path for the abstraction (adding a generic abstraction to Array) instead of creating a custom object. Mar 24, 2014 at 12:17

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.

• Thank you. I maybe wrong, but I can not see a scenario where a loner is left. The number of santas should always be equal to the number of players. So every santa will be matched with player other than himself. How can a loner be left over? Mar 24, 2014 at 4:34
• Take your example: { Mohamad, Carolina, Sami, Tania, Ikram, José }. Let's say the first five form a cycle: Mohamad → Carolina, Carolina → Sami, Sami → Tania, Tania → Ikram, Ikram → Mohamad. Poor José is a loner and would have to be assigned to himself. Mar 24, 2014 at 6:14
• I see. But doesn't your implementation of the random_player_for leave the chance of duplicate assignments? No where I see we are modifying the player array. So what's to stop the same player being picked on another iteration? Perhaps we should change return others.sample to players.delete(others.sample)? Mar 24, 2014 at 12:02