Partitioning students into teams, brute force approach

student_teams.rb

require 'pp'
require 'set'

# Which days are students available?
STUDENTS = [
  # Mon.   Tue.   Wed.  Thurs.  Fri.
  [ true,  true, false, false, false], # Student 1
  [ true, false, false, false, false], # Student 2
  [false,  true,  true, false, false], # etc ...
  [false,  true, false,  true,  true],
  [ true, false, false, false,  true],
  [ true, false, false, false, false],
  [ true,  true, false, false, false],
  [ true,  true,  true,  true,  true],
  [ true,  true,  true,  true,  true],
  [ true,  true,  true,  true,  true],
  [ true,  true,  true,  true,  true],
  [ true,  true,  true,  true,  true],
  [ true,  true,  true,  true,  true],
  [ true,  true,  true,  true,  true],
  [ true,  true,  true,  true,  true],
  [ true,  true,  true,  true,  true]
]
TEAM_SIZE = 6

# Takes `partitions`, a set of arrays of student numbers (see above).
# Each array in the set is a *partition* of the set of all students.
#
# It returns an integer "score", the number of partitions that are
# "compatible", i.e. there is at least one day on which all the
# students in that partition can meet.
#
def score(partitions)
  scores = partitions.map { |p|
    pdata = p.map { |n| STUDENTS[n - 1] }
    scor = 0
    0.upto(4) do |i|
      if pdata.map { |datum| datum[i] }.all?
        scor = 1
        break
      end
    end
    scor
  }
  scores.reduce(0) { |a,e| a = a + e }
end

# Stolen from bit.ly/1KqaRbm
module MarcAndreLafortune
  def self.enum(n, k)
    # Pick smaller_size items from the list, repeat smaller_n times
    # then pick larger_size items from the list, repeat larger_n times.
    smaller_n = n.div k
    larger_times = n % k
    smaller_times = k - larger_times
    larger_n = smaller_n + 1

    return to_enum(:enum, n, k) { calc_size(n, smaller_n, smaller_times, larger_n, larger_times) } unless block_given?

    all = [*1..n]
    # split all into one subset to group with the smaller_n and another
    # to group with the larger_n.
    all.combination(smaller_n * smaller_times).each do |smaller|
      larger = all - smaller
      subdivide(smaller, smaller_n) do |small|
        subdivide(larger, larger_n) do |large|
          yield [*small, *large]
        end
      end
    end
  end

  # Subdivides elems into groups of n, keeping the elements sorted
  # and generating only the sorted such combinations.
  def self.subdivide(elems, n)
    return yield [] if elems.empty?
    # No choice for the first element, because we want to keep things sorted.
    first, *rest = elems
    rest.combination(n - 1).each do |comb|
      remain = rest - comb
      subdivide(remain, n) do |sub|
        yield [[first, *comb], *sub]
      end
    end
  end
end

n_students = STUDENTS.length
puts format("Number of students: %d", n_students)
puts format("Team size: %d", TEAM_SIZE)
n_teams = (n_students.to_f / TEAM_SIZE).ceil
puts format("Number of teams: %d", n_teams)
possibilities = MarcAndreLafortune.enum(n_students, n_teams).to_a
puts format("Ways to partition students: %d", possibilities.length)
best = possibilities.max { |pby| score(pby) }
puts format("Best scoring possibility: %s", best.to_a)
puts format("Score: %d", score(best))