Предположим, я хотел бы назначить 3 студентов по 3 темам. Студенты могут оценивать каждую тему от 1 до 3. Добавлено позже: ни в одной теме не может быть более 2 студентов.
Возможными заданиями для студентов являются следующие перестановки (которые включают в себя случаи, когда в теме участвуют три ученика, но игнорируют их), где каждый равен
(студент 1 тема, студент 2 тема, студент 3 тема)
Обратите внимание, что трех студентов не нужно назначать на разные темы.
n_topics = 3
n_students = 3
per = [el for el in itertools.product(range(n_topics), repeat=n_students)]
У нас также есть рейтинг студентов
rankings = [{0:1, 1:3, 2:2}, #student 1
{0:3, 1:1, 2:2}, #student 2
{0:2, 1:1, 2:3}] # ...
Следовательно, естественно, чтобы ранжирование было стоимостью. Таким образом, если учащийся занимает первое место по теме и получает назначение на эту тему, он оплачивает минимальную стоимость 1. Если он занимает третье место и получает назначение, он оплачивает стоимость 3.
Найти лучшие 3 перестановки
def get_cost(perm, rankings):
cost = 0
for (el, c) in zip(perm, rankings):
cost += c[el]
return cost
def get_best_perms(per, rankings):
perm_cost = {}
for perm in per:
perm_cost[perm] = get_cost(perm, rankings)
return sorted(perm_cost.items(), key=operator.itemgetter(1))[0:3]
Лучше всего дать первому студенту нулевую тему, а вторым двум студентам - вторую тему, чтобы минимизировать стоимость.
print(get_best_perms(per, rankings))
#[((0, 1, 1), 3), ((0, 2, 1), 4), ((0, 1, 0), 4)]
На самом деле, однако, есть 13 учеников и 7 тем, поэтому 7 ** 13 = 96889010407 перестановок (в этом случае ни в одной теме не может быть более 4 учеников, и некоторые темы могут быть не выбраны)
Есть ли у кого-нибудь совет (какие библиотеки использовать и т. Д.), Как распараллелить этот код (поскольку каждая стоимость может быть рассчитана независимо от других)? Или как вообще его ускорить?
Я думаю, что это проблема типа коммивояжера, но у меня так мало учеников и тем, которые я подумала, что можно попытаться попробовать все варианты, но моя интуиция на то время, которое может потребоваться для этого вещь не очень хорошая.
Спасибо за ваше время
*** Если есть лучшее место для репоста, пожалуйста, дайте мне знать!