python - 如何创建分配问题成本矩阵

Question

我有 250 个项目和 50 名主管。我们的 130 名学生中的每一个都将他们首选的项目从 1 到 5 （1 是最喜欢的）进行排名，并且不给其他 245 分。我想为每个学生分配一个主管，但一个主管最多只能有 12 名学生。

我正在尝试制作一些虚拟数据，但努力制作成本矩阵。

用大小为 (5 x 5) 的随机整数定义一个矩阵。

import random

def createMatrix(n):
    firstRow = random.sample(range(n),n)
    permutes = random.sample(range(n),n)
    return list(firstRow[i:]+firstRow[:i] for i in permutes)


N = 5
m = createMatrix(N)
for i in m:
    print(i)

[1, 0, 3, 4, 2]
[3, 4, 2, 1, 0]
[4, 2, 1, 0, 3]
[2, 1, 0, 3, 4]
[0, 3, 4, 2, 1]

但这是一个拉丁方阵，我想允许一些行包含重复的值，表示两个学生对给定的同一个项目排名相同的值。任何想法将不胜感激。

标签： python

Answer 1

你有 130 个students并且想要一些重复的选择。因此，生成 fe 110 个选择（重复的可能性很小 - 但 250 个中的 5 个并不多）。然后选择一些生成的选项作为 dupe-candidates 并再次添加其中一些选项，直到您获得 130 个选项：

from random import sample,shuffle

projects = 250
students = 130
dup_choices = 20   # means we generate 110 choices and at least 20 will be dupes
per_dup = 5        # add up to this amount of dupes for each dupe candidate

un_duped = students - dup_choices 

# random samples
student_choices = [ sample(range(projects), k = 5) for _ in range(un_duped)]
# select dupe candidates
dups = sample(student_choices, k = max(0, dup_choices // per_dup) + 1)

# add enough of each duplicate to statisfy your numbers
for d in dups:
    student_choices.extend( (d.copy() for _ in range(per_dup) ) )

# integer rounding + 1 => you will overshoot - so trim back to number of students
student_choices = student_choices[:students]

# mix the dupes into the data
# shuffle(student_choices)

这将产生 130 种选择，其中至少 20 种是其他一些的某种重复。

您根据这些数据创建成本矩阵 - 学生选择中项目编号的位置是其优先级（0 == 1st，1 = 2nd，...）：

costs = [[0 if pr not in choice else choice.index(pr) + 1 
            for pr in range(projects)]
         for choice in student_choices]



# print first 3 of choices / costs
for sc in student_choices[:3]:
  print(sc)

for c in costs[:3]:
    print (c)

输出：

[124, 174, 43, 181, 63]

[158, 110, 129, 120, 149]

[226, 238, 183, 249, 90]

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4]