Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Partitioning students into teams, brute force approach
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))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment