python - 在不同的日子随机分配一组人时最好的方法是什么？
问题描述
所以，我有一个有趣的问题。但不确定这里是否是我必须发布的地方。
上下文
基本上我想建立不同的学习小组
- 拥有多名学生
- 拥有多名导师
但是，每个人在一周中都有一组可用的日子来参加一个学习课程。每个人只能参加一个学习小组
可用性示例
StudentA = [Tuesday, Wednesday]
StudentB = [Wednesday, Saturday]
StudentC = [Saturday]
TutorA= [Tuesday, Friday]
TutorB = [Tuesday]
我必须让学习小组
- 有 2 到 4 名学生
- 有 2 到 3 位导师
我的方法
我正在使用 python 3 我正在尝试生成所有可能的组合并使用可用人员列表过滤实际可能的情况：
我用代码命名每个学生可用性组合：
- [星期二] => "p1"
- [星期三] => "p2"
- ...
- [周二、周三、周四] => "p7"
和导师一样
- [星期二] => "c1"
- [星期三] => "c2"
- ...
- [周二、周三、周四] => "c7"
我使用 itertools.combinations_with_replacement 来制作所有
- 学生组合
- 导师组合
我将之前的两种组合组合成可能的研究组
我结合所有团队来生成场景
我使用限制过滤
- 每个人被分配在一个研究组中
- 每个人只参加一次
- 学生比导师多
问题
正如人们所预料的那样，组合和排列正在产生大量的可能性。
我可以接受将天数限制为三天。
但是我仍然无法为我的普通计算机提供可接受的性能
有没有更好的方法我没有看到？我在想象一些线性代数是否可以将这个问题转化为一组方程，但不确定
Obs：学生和导师的人数要多得多（每个人在 20 到 50 人之间）
解决方案
上下文
按每周 7 天的可用性指定学生
例子：
[
[1, 1, 0, 0, 0, 0, 0],
[1, 0, 1, 0, 0, 0, 1],
[1, 1, 0, 1, 0, 1, 1],
[0, 1, 0, 1, 0, 1, 0]
]
每行代表一个学生（本例中为 4 个学生） 每列代表一周中的某一天（即 7 个），分别为可用或不可用的 1 或 0。
所以[1, 1, 0, 0, 0, 0, 0]意味着学生 0 在一周的前两天（即周一和周二）有空。
TA 可用性以类似方式指定
例子：
[
[1, 1, 1, 1, 1, 1, 1],
[1, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 1]
]
显示有三个助教，每天都有第一个助教。
会议安排如下：
7 Days with N sessions per day numbered 0 to N-1
Session Monday Tuesday Wednesday Thursday Friday Saturday Sunday
0 session session session session session session session
1 session session session session session session session
2 session session session session session session session
3 session session session session session session session
...
N-1 session session session session session session session
N 是未知的，但我们可以选择一个适当大的值（即，如果 N 得到只是导致更多的会话没有分配给学生或助教）。
约束是：
- 每节 2 至 4 名学生
- 学生每周只有一堂课
- 学生只在他们可用的日子被分配一个会话
- 每个会话 2 到 3 个助教
- 助教仅在其可用的日期分配会话
目标是找到满足约束的学生和助教的作业。
方法
使用 Google ortools 约束求解器
ortools 允许将此组合问题描述为搜索问题
代码
from ortools.sat.python import cp_model # Google Constraint Modeling Tool (https://developers.google.com/optimization/cp/cp_solver)
from tabulate import tabulate # For displaying results in table form (https://pypi.org/project/tabulate/)
week_days = ("Monday","Tuesday","Wednesday","Thursday","Friday","Saturday","Sunday")
def main(student_availability, ta_availability):
########################################################
# Information Setup
########################################################
num_days = len(week_days) # days in a week we are using
num_students = len(student_availability)
num_days = len(student_availability[0])
all_students = range(num_students)
all_days = range(num_days)
# Show student availability
special = u'\u2713'
tmp_table = [[special if c else 'x' for c in row] for row in student_availability]
display_table(tmp_table, "Students", "Students Availability")
num_tas = len(ta_availability)
all_tas = range(num_tas)
# Show TA availability
tmp_table = [[special if c else 'x' for c in row] for row in ta_availability]
display_table(tmp_table, " TAs", "\nTA Availability")
# Learning sessions
# Model as max sessions per day, 7 days a weeks
# The solver will decide which sessions are assigned students and TAs
max_sessions_per_day = num_students # Would actually use a lot fewer sessions per day
all_sessions = range(max_sessions_per_day)
########################################################
# Creates the model
########################################################
model = cp_model.CpModel()
########################################################
# Specify Constraints
########################################################
session_zero = {} # sessions with zero students and TAs (i.e. unused)
session_bound = {} # sessions which satisfy the student and TA occupancy bounds
for d in all_days:
for session in all_sessions:
session_zero[(d, session)] = model.NewBoolVar('zero%id%ig' % (d, session))
session_bound[(d, session)] = model.NewBoolVar('bound%id%ig' % (d, session))
model.Add(session_zero[(d, session)] + session_bound[(d, session)]==1) # Sessions are used or unused
# Student Constraints
student_group = {}
for s in all_students:
for d in all_days:
for session in all_sessions:
student_group[(s, d, session)] = model.NewBoolVar('student_assigned%is%id%ig' % (s, d, session))
# Each used session has between 2 & 4 students
for d in all_days:
for session in all_sessions:
# Meeting define by (d, session)
students_assigned = sum(student_group[(s, d, session)] for s in all_students)
model.Add(students_assigned==0).OnlyEnforceIf(session_zero[(d, session)])
model.Add(students_assigned >= 2).OnlyEnforceIf(session_bound[(d, session)])
model.Add(students_assigned <= 4).OnlyEnforceIf(session_bound[(d, session)])
# Every student is assigned one session in the week on their available days
for s, row in enumerate(student_availability):
available_days = [d for d, v in enumerate(row) if v > 0]
model.Add(sum(student_group[(s, d, session)] for d in available_days for session in all_sessions) == 1)
# No Studentss are assigned sessions on their unavailable days
for t, row in enumerate(student_availability):
unavailable_days = [d for d, v in enumerate(row) if v == 0]
model.Add(sum(student_group[(t, d, session)] for d in unavailable_days for session in all_sessions) == 0)
# TA Constraint
ta_group = {}
for t in all_tas:
for d in all_days:
for session in all_sessions:
ta_group[(t, d, session)] = model.NewBoolVar('ta_assigned%is%id%ig' % (t, d, session))
# Each session has between 2 & 3 TAs
for d in all_days:
for session in all_sessions:
ta_assigned = sum(ta_group[(t, d, session)] for t in all_tas)
model.Add(ta_assigned==0).OnlyEnforceIf(session_zero[(d, session)])
model.Add(ta_assigned >= 2).OnlyEnforceIf(session_bound[(d, session)])
model.Add(ta_assigned <= 3).OnlyEnforceIf(session_bound[(d, session)])
# TAs are assigned on available days
for t, row in enumerate(ta_availability):
available_days = [d for d, v in enumerate(row) if v > 0]
model.Add(sum(ta_group[(t, d, session)] for d in available_days for session in all_sessions) >= 0)
# No TAs are assigned on their unavailable days
for t, row in enumerate(ta_availability):
unavailable_days = [d for d, v in enumerate(row) if v == 0]
model.Add(sum(ta_group[(t, d, session)] for d in unavailable_days for session in all_sessions) == 0)
# Creates the solver and solve.
solver = cp_model.CpSolver()
# Sets a time limit of 10 seconds.
solver.parameters.max_time_in_seconds = 10.0
# Display the first five solutions.
a_few_solutions = range(2)
solution_printer = StudentsPartialSolutionPrinter(student_group,
num_students,
ta_group,
num_tas,
num_days,
max_sessions_per_day,
student_availability,
ta_availability,
a_few_solutions)
status = solver.Solve(model, solution_printer)
print()
print('Status = %s' % solver.StatusName(status))
print('Number of solutions found: %i' % solution_printer.solution_count())
# Statistics.
print()
print('Statistics')
print(' - conflicts : %i' % solver.NumConflicts())
print(' - branches : %i' % solver.NumBranches())
print(' - wall time : %f s' % solver.WallTime())
print(' - solutions found : %i' % solution_printer.solution_count())
class StudentsPartialSolutionPrinter(cp_model.CpSolverSolutionCallback):
"""Print intermediate solutions."""
def __init__(self,
student_group,
num_students,
ta_group,
num_tas,
num_days,
max_sessions_per_day,
student_availability,
ta_availability,
sols):
cp_model.CpSolverSolutionCallback.__init__(self)
self._student_group = student_group
self._num_students = num_students
self._ta_group = ta_group
self._num_tas = num_tas
self._num_days = num_days
self._max_sessions_per_day = max_sessions_per_day
self._student_availability = student_availability
self._ta_availability = ta_availability
self._solutions = set(sols)
self._solution_count = 0
def on_solution_callback(self):
if self._solution_count in self._solutions:
print('\nSolution %i' % self._solution_count)
# Student Scheduling
table = [[u'\u2713' if col else 'x' for col in row] for row in self._student_availability]
for session in range(self._max_sessions_per_day):
for d in range(self._num_days):
for s in range(self._num_students):
if self.Value(self._student_group[(s, d, session)]):
table[s][d] = table[s][d] + f" {week_days[d][:3]}-{session}"
print()
display_table(table, "Students", "Students Scheduling")
# TA scheduling
table = [[u'\u2713' if col else 'x' for col in row] for row in self._ta_availability]
for session in range(self._max_sessions_per_day):
for d in range(self._num_days):
for s in range(self._num_tas):
if self.Value(self._ta_group[(s, d, session)]):
table[s][d] = table[s][d] + f" {week_days[d][:3]}-{session}"
print()
display_table(table, " TAs", "TA Scheduling")
self._solution_count += 1
def solution_count(self):
return self._solution_count
def display_table(data, data_category, message):
''' Display data in tabular form'''
table = [[f'{idx:>8}'] + row for idx, row in enumerate(data)]
print(message)
print(tabulate(table, headers=(data_category,) + week_days, tablefmt="rst"))
if __name__ == '__main__':
# Student Information
student_availability = [
[1, 1, 0, 0, 0, 0, 0],
[1, 0, 1, 0, 0, 0, 1],
[1, 1, 0, 1, 0, 1, 1],
[0, 1, 0, 1, 0, 1, 0]
]
# TA Information
ta_availability = [
[1, 1, 1, 1, 1, 1, 1],
[1, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 1, 0, 0, 1]
]
# Find solutions
main(student_availability, ta_availability)
输出
指定的问题需要三个会话——星期一 (Mon-3) 和星期四 (Thu-0)。
Students Availability
========== ======== ========= =========== ========== ======== ========== ========
Students Monday Tuesday Wednesday Thursday Friday Saturday Sunday
========== ======== ========= =========== ========== ======== ========== ========
0 ✓ ✓ x x x x x
1 ✓ x ✓ x x x ✓
2 ✓ ✓ x ✓ x ✓ ✓
3 x ✓ x ✓ x ✓ x
========== ======== ========= =========== ========== ======== ========== ========
TA Availability
========== ======== ========= =========== ========== ======== ========== ========
TAs Monday Tuesday Wednesday Thursday Friday Saturday Sunday
========== ======== ========= =========== ========== ======== ========== ========
0 ✓ ✓ ✓ ✓ ✓ ✓ ✓
1 ✓ x x x x x x
2 ✓ x x ✓ x x ✓
========== ======== ========= =========== ========== ======== ========== ========
Solution 0
Students Scheduling
========== ======== ========= =========== ========== ======== ========== ========
Students Monday Tuesday Wednesday Thursday Friday Saturday Sunday
========== ======== ========= =========== ========== ======== ========== ========
0 ✓ Mon-3 ✓ x x x x x
1 ✓ Mon-3 x ✓ x x x ✓
2 ✓ ✓ x ✓ Thu-0 x ✓ ✓
3 x ✓ x ✓ Thu-0 x ✓ x
========== ======== ========= =========== ========== ======== ========== ========
TA Scheduling
========== ======== ========= =========== ========== ======== ========== ========
TAs Monday Tuesday Wednesday Thursday Friday Saturday Sunday
========== ======== ========= =========== ========== ======== ========== ========
0 ✓ Mon-3 ✓ ✓ ✓ Thu-0 ✓ ✓ ✓
1 ✓ Mon-3 x x x x x x
2 ✓ x x ✓ Thu-0 x x ✓
========== ======== ========= =========== ========== ======== ========== ========
Status = OPTIMAL
Number of solutions found: 1
Statistics
- conflicts : 0
- branches : 0
- wall time : 0.014649 s
- solutions found : 1
推荐阅读
- javascript - 如何创建一个承诺队列，当它为空时将同步？
- excel - Excel - 从列表中搜索字符串，区分大小写和通配符
- regex - 删除 Nifi 中的列
- sql - 使用 Snowflake 中多列值的 SQL 计数和转置表输出
- javascript - 为具有重复名称的对象标记白名单
- c++ - 当我更改 XAxis 和 YAxis 时，QChart 点绘制不正确
- javascript - 有没有办法使用 JavaScript 更改 ::selection （选定文本）的背景颜色？
- javascript - 显示正确交货日期的问题
- javascript - 如何避免单击按钮时复制输入值
- python - IntelliJ 选择解释器以查看已安装的包