[Math] An efficient approach to combinations of pairs in groups without repetitions

combinationscombinatoricsgenerating-functions

Before I start, I need to admit that I am not a mathematician and if possible would need this explained in laymen terms. I appreciate your patience with this.

The problem: A class consisting of n students whom I'd like to pair up throughout the school year.

The number of pairs is n/2. I'd like to maximize students working with new people as much as possible, and so exhaust all possible combinations. Permutations don't matter — student 1 + student 2 is same as student 2 + student 1.

What is an efficient way to build all non-repeating combinations of pairs?

One way, (suggested by Aleksei Malushkin), is to find all unique pairs, then all combinations of n/2 pair groups by brute-forcing out all non-valid groups.

Finding all unique pairs is trivial in Ruby: [1,2,3,4,5,6,7,8].combination(2).to_a provides an array of all 2-item pairs.

What I need, however, is to produce all groups consisting of 4 pairs each, each group without repetition of students. If the class consists of 20 students, I will need all groups of 10 pairs.

The bruteforce approach creates all combinations of pairs and throws away the ones containing repeating pairs, but this falls apart very quickly with higher numbers of students.

Here's the ruby code which solves for 8 students:

# Ruby 2.5.3

students = [1,2,3,4,5,6,7,8]
possible_pairs = students.combination(2).to_a  # https://ruby-doc.org/core-2.4.1/Array.html#method-i-combination

puts "Possible pairs: (#{possible_pairs.size}) #{possible_pairs}"
puts "Possible pair combinations: #{possible_pairs.combination(a.size/2).size}"

groups_without_repetition = possible_pairs.
combination(students.size/2).                     # create all possible groups with students.size/2 (4) members each
each_with_object([]) do |group, accumulator|      # with each of these groups, and an "accumulator" variable starting as an empty array

  next unless group.flatten.uniq.length == (students.size)  # skip any group with repeating elements
  next if accumulator.find {|existing_group| existing_group & group != []}      # skip any group that may be found in the accumulator

  accumulator << group  # add any non-skipped group to the accumulator
end # returnn the value of the accumulator and assign it to groups_without_repetition

puts "actual pair combinations without repetition (#{groups_without_repetition.size}):"

groups_without_repetition.each_with_index do |arr, i|
  puts "#{i+1}: #{arr}"
end

When run, this returns:

Possible pairs: (28) [[1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [1, 7], [1, 8], [2, 3], [2, 4], [2, 5], [2, 6], [2, 7], [2, 8], [3, 4], [3, 5], [3, 6], [3, 7], [3, 8], [4, 5], [4, 6], [4, 7], [4, 8], [5, 6], [5, 7], [5, 8], [6, 7], [6, 8], [7, 8]]
Possible pair combinations: 376740
actual pair combinations without repetition (7):
1: [[1, 2], [3, 4], [5, 6], [7, 8]]
2: [[1, 3], [2, 4], [5, 7], [6, 8]]
3: [[1, 4], [2, 3], [5, 8], [6, 7]]
4: [[1, 5], [2, 6], [3, 7], [4, 8]]
5: [[1, 6], [2, 5], [3, 8], [4, 7]]
6: [[1, 7], [2, 8], [3, 5], [4, 6]]
7: [[1, 8], [2, 7], [3, 6], [4, 5]]

It is however not efficient. With only 12 students, the possible pairs are 66, and the possible pair combinations 90858768. I am looking to apply this to a class with 80+ participants so this approach is clearly not going to work.

Question 1: What would be an efficient approach to construct these combinations?

Looking at the results, it seems to me that the number of valid groups is n/2 – 1, as a student can only belong to one of n/2 possible pairs.

My sense is that it would be more efficient to construct only the valid groups_without_repetition instead of creating all possible groups and throwing out the non-valid ones. I am not sure how to approach this process, and would appreciate your help.

Question 2: How to approach this with an odd number of students?

This may need to be a separate discussion so I would not worry about it unless it has a known solution.

a. In a case where one of the students will have to participate twice to accommodate the odd number

b. In a case where one of the pairs would become a trio

In each of these cases, the students who were a part of the above non-conventional pairings, should be excluded from further exceptions for as many rotations as possible.

Edit: Posting a Ruby-based solution, based on Alexander Burstein's answer

class SafeArray < Array

  # make it possible to return items from the beginning of the array when
  # the item's index exceeds the size of the array. 
  # Ruby does this automatically for negative indexes.

  def [](i)
    if i > size-1
      super(i % size)
    else
      super(i)
    end
  end

end


class AllGroups

  attr_reader :items, groups

  def initialize(items)
    @items = items
  end

  def generate!
    @groups = []

    return if items.size < 2
    return @groups = [[ items[0], items[1] ]] if items.size < 4

    n = items.size
    infinity_point = items[0]

    candidates = SafeArray.new( items[1..-1] )


    (0..n-2).each do |i|
      group = []

      group << [infinity_point, candidates[i]]  # first pair

      (1..(n/2 - 1)).each do |k|
        current_pair = [ candidates[i+k], candidates[i-k] ]
        group << current_pair
      end

      @groups << group

    end
  end

end

# run with 8 "students"

students = %w{1 2 3 4 5 6 7 8}

all_groups = AllGroups.new(students)
all_groups.generate!

all_groups.groups.each_with_index do |g, i|
  puts "#{i+1}: #{g}"
end

# results:

# 1: [["1", "2"], ["3", "8"], ["4", "7"], ["5", "6"]]
# 2: [["1", "3"], ["4", "2"], ["5", "8"], ["6", "7"]]
# 3: [["1", "4"], ["5", "3"], ["6", "2"], ["7", "8"]]
# 4: [["1", "5"], ["6", "4"], ["7", "3"], ["8", "2"]]
# 5: [["1", "6"], ["7", "5"], ["8", "4"], ["2", "3"]]
# 6: [["1", "7"], ["8", "6"], ["2", "5"], ["3", "4"]]
# 7: [["1", "8"], ["2", "7"], ["3", "6"], ["4", "5"]]

```

Best Answer

In graph theory terms, you would like to partition a complete graph into matchings ($1$-regular graphs). There is a well-known algorithm for doing that. Your students would be the vertices of this graph, and a pair of students working together would be an edge of this graph.

First, label your $n$ students (where $n$ is even) as follows: $\infty,0,1,2,\dots,n-2$. Think of the finite (non-$\infty$) labels as remainders modulo $n-1$. Now, for each $i=0,1,2,\dots,n-2$, pair your students as follows: $(\infty,i)$ and $(i+k,i-k)$ for $k=1,2,\dots,\frac{n}{2}-1$. In other words, except for the special pair with $\infty$, the sum of the two labels in a pair should be $2i$ modulo $n-1$.

For example, let $n=8$, then $n-1=7$ (so all labels are remainders modulo $7$), and your vertex labels are $\infty,0,1,2,3,4,5,6$. The matchings you need are as follows:

$$ \begin{matrix} i=0: & (\infty,0), (1,6), (2,5), (3,4)\\ i=1: & (\infty,1), (2,0), (3,6), (4,5)\\ i=2: & (\infty,2), (3,1), (4,0), (5,6)\\ i=3: & (\infty,3), (4,2), (5,1), (6,0)\\ i=4: & (\infty,4), (5,3), (6,2), (0,1)\\ i=5: & (\infty,5), (6,4), (0,3), (1,2)\\ i=6: & (\infty,6), (0,5), (1,4), (2,3) \end{matrix} $$

To see that this as a picture, imagine the labels $0,1,2,\dots,n-2$ as spaced evenly around a circle while $\infty$ is placed in the center. Then $(\infty,i)$ is a "minute hand" pointing at $i$, while the rest of the pairs are all edges perpendicular to it.

Related Question