How to select random pairs in ruby, without duplicating pairs

Question

I would like to pick 2 names at random from an array, do this for all names in the array, and make sure nobody gets teamed up with the same person twice. After everybody has been teamed up once with each other person the big cycle restart.

I found the .sample method to pull 2 names from an array at random. [“Sander”, “Sjaak”, “Timo”, “Ernst”, “Floris”, “Wayne”, “Arno”, “Henk”, “Rob”].sample(2)

But how do I make sure people don't get teamed up with the same person the next day?

Answer 1

This is the way chessplayers play a all-play-all tournament. It is called a "round-robin tournament". Wikipedia has an algorithm. The array could be shuffled beforehand. This is an implementation of the wikipedia article:

names = ["Sander", "Sjaak", "Timo", "Ernst", "Floris", "Wayne", "Arno", "Henk", "Rob"]

n = names.dup #n is going to be mutated, leave names intact
n << "Dummy" if n.size.odd?
fixed_name = n.shuffle!.pop

n.size.times do |i| #n.size is one less than the number of participants
  puts "round #{i+1}"
  two_rows = [[fixed_name]+n[0..n.size/2-1], n[n.size/2..-1].reverse]
  pairs = two_rows.transpose.shuffle # the shuffle is optional, just cosmetic
  pairs.each{|c| p c }
  n.rotate!
  puts
end

output:

round 1
["Arno", "Floris"]
["Wayne", "Dummy"]
["Sander", "Sjaak"]
["Henk", "Rob"]
["Ernst", "Timo"]

round 2
["Wayne", "Sjaak"]
["Dummy", "Rob"]
["Ernst", "Arno"]
["Henk", "Floris"]
["Sander", "Timo"]

round 3
["Wayne", "Timo"]
["Henk", "Arno"]
["Rob", "Sjaak"]
["Ernst", "Sander"]
["Dummy", "Floris"]

round 4
["Wayne", "Sander"]
["Sjaak", "Floris"]
["Dummy", "Arno"]
["Rob", "Timo"]
["Ernst", "Henk"]

round 5
["Sjaak", "Arno"]
["Dummy", "Henk"]
["Floris", "Timo"]
["Rob", "Sander"]
["Ernst", "Wayne"]

round 6
["Ernst", "Dummy"]
["Timo", "Arno"]
["Rob", "Wayne"]
["Sjaak", "Henk"]
["Floris", "Sander"]

round 7
["Timo", "Henk"]
["Sjaak", "Dummy"]
["Floris", "Wayne"]
["Ernst", "Rob"]
["Arno", "Sander"]

round 8
["Ernst", "Sjaak"]
["Sander", "Henk"]
["Arno", "Wayne"]
["Floris", "Rob"]
["Timo", "Dummy"]

round 9
["Sander", "Dummy"]
["Ernst", "Floris"]
["Henk", "Wayne"]
["Arno", "Rob"]
["Timo", "Sjaak"]

Answer 2

Starting with an array of names:

names = ["Sander", "Sjaak", "Timo", "Ernst", "Floris", "Wayne", "Arno", "Henk"]

You'll want to shuffle them and group them into pairs:

shuffled = names.shuffle.each_slice(2).to_a
#=> [["Timo", "Sjaak"], ["Henk", "Arno"], ["Sander", "Ernst"], ["Wayne", "Floris"]] 

Looks good so far, but this will be a problem later on because order matters for arrays. For example, ["Timo", "Sjaak"] is considered different from ["Sjaak", "Timo"]. We can fix this by turning the arrays into Sets. Order doesn't matter when determining if two Sets are equal.

shuffled = names.shuffleeach_slice(2).map { |group| Set.new(group) }
#=> [#<Set: {"Arno", "Wayne"}>, #<Set: {"Henk", "Timo"}>, #<Set: {"Ernst", "Floris"}>, #<Set: {"Sander", "Sjaak"}>] 

The tricky part is ensuring that each day, you have no repeats. You could have "rules" to prevent this, but then your algorithm would no longer be random. The only way to ensure complete randomness is to check for duplicates and reshuffle. Let's say you already have one day's groups saved to yesterday and you want a new group. You can do the following:

loop do
  today = names.shuffle.each_slice(2).map { |group| Set.new(group) }
  break if (today & yesterday).empty?
end

The today & yesterday part is called a "Set intersect." It will return a new array containing only the groups which are the same in today and yesterday. If no groups are the same (meaning there are no repeats), then the array will be empty.

The only thing left is to figure out how to save yesterday's group so you can use it to check against today's group. If you're working within a set timeframe (e.g. a teacher creating student groups for the semester), then you can just calculate an entire semester's worth of groups all at once. Otherwise, you'll probably have to save the previous day's group to a text file so you can access it later.