针对不同规模群体和有限场所的稳定匹配算法
stable match algorithm for different sizes groups and limited places
我想编写一个程序，根据学生的选择和专业范围，将学生引导到他们在大学的专业。
每个专业可以招收多个学生（本例cnm =1，dsi=2，rss=2），学生人数可以多于名额（本例一个学生不可以）一个地方，因为只有 5 个地方）。
程序运行没有问题但输出不正确。（我不知道为什么）
.
此示例的输出应为 ((a,cnm),(c,rss),(b,dsi),(e,dsi),(f,rss))
我在 youtube (https://youtu.be/FhRf0j068ZA ,the source code https://github.com/Schachte/stable-matching-algorithm) 上找到了一个视频，其中有人解释并编写了稳定匹配问题的代码，我喜欢那个代码，所以我接受了它，并尝试对其进行编辑，以便它可以解决我的问题问题
如果有人能帮助我，我将不胜感激。
*****这是我的代码
students = {
'A': ['CNM', 'DSI', 'RSS'],
'B': ['CNM', 'DSI', 'RSS'],
'C': ['DSI', 'CNM', 'RSS'],
'D': ['DSI', 'RSS', 'CNM'],
'E': ['RSS', 'DSI', 'CNM'],
'F': ['RSS', 'CNM', 'DSI']
}
choices = {
'DSI': ['C', 'E','D', 'B','F','A'],
'RSS': ['B','F','A', 'E', 'D','C'],
'CNM': ['A', 'B','C', 'D','E','F']
}
rss=2
cnm = 1
dsi=2
results = []
students_with_out_choice =[]
for student in students:
students_with_out_choice.append(student)
while (len(students_with_out_choice) > 0 ):
for i in range (3):
for student in students_with_out_choice:
for choice in students[student]:
if ((choice == "DSI" and dsi != 0) or (choice == "RSS" and rss != 0) or (choice == "CNM" and cnm != 0)):
results.append([student, choice])
students_with_out_choice.remove(student)
if (choice == "DSI"):
dsi -= 1
if (choice == "RSS"):
rss -= 1
if (choice == "CNM"):
cnm -= 1
break
else:
for key, value in results:
if choice == value:
a= key
etudiant_actuel = choices[choice].index(a)
etudiant_proposer = choices[choice].index(student)
if (etudiant_actuel >etudiant_proposer):
students_with_out_choice.remove(student)
students_with_out_choice.append(a)
a = student
break
elif(i==2):
students_with_out_choice.remove(student)
break
print(results)
您的代码中的一个问题可能是您在迭代列表 (students_with_out_choice) 时更改了它。这通常会导致意想不到的结果。
正如@enke 所指出的，延迟接受算法是此处选择的方法。这个算法的实现在你的例子中看起来像这样：
s = {
'A': ['CNM', 'DSI', 'RSS'],
'B': ['CNM', 'DSI', 'RSS'],
'C': ['DSI', 'CNM', 'RSS'],
'D': ['DSI', 'RSS', 'CNM'],
'E': ['RSS', 'DSI', 'CNM'],
'F': ['RSS', 'CNM', 'DSI']
}
r = {
'DSI': ['C', 'E', 'D', 'B', 'F', 'A'],
'RSS': ['B', 'F', 'A', 'E', 'D', 'C'],
'CNM': ['A', 'B', 'C', 'D', 'E', 'F']
}
p = {
'DSI': 2,
'RSS': 2,
'CNM': 1
}
def get_matched_students(students, rankings, places):
waiting_students = [student for student in students]
matching_results = {choice: [] for choice in places}
def get_waiting_list_without_student(student):
return [x for x in waiting_students if x != student]
def get_sorted_results_with_student(student, choice):
matching_results[choice].append(student)
return [x for x in rankings[choice] if x in matching_results[choice]]
while waiting_students:
for student in waiting_students.copy():
if not students[student]:
waiting_students = get_waiting_list_without_student(student)
continue
choice = students[student].pop(0)
if len(matching_results[choice]) < places[choice]:
matching_results[choice] = get_sorted_results_with_student(student, choice)
waiting_students = get_waiting_list_without_student(student)
else:
if rankings[choice].index(student) < rankings[choice].index(matching_results[choice][-1]):
matching_results[choice] = get_sorted_results_with_student(student, choice)
waiting_students = get_waiting_list_without_student(student)
waiting_students.append(matching_results[choice].pop())
return matching_results
print(get_matched_students(s, r, p))
这将为您提供与每个科目匹配的学生列表：{'DSI': ['C', 'E'], 'RSS': ['B', 'F'], 'CNM': ['A']}
如果你想从学生的角度来看结果，你可以这样做：
results = get_matched_students(s, r, p)
results_by_students = [[student, course] for student in s for course, result in results.items() if student in result]
print(results_by_students)
# Output: [['A', 'CNM'], ['B', 'RSS'], ['C', 'DSI'], ['E', 'DSI'], ['F', 'RSS']]
我最终使用两种不同的解决方案解决了我的问题。
第一个解决方案是在我的第一个程序中发现了错误并进行了更正。
students = {
'A': ['DSI', 'RSS', 'CNM'],
'B': ['RSS', 'DSI', 'CNM'],
'C': ['CNM', 'DSI', 'RSS'],
'D': ['DSI', 'RSS', 'CNM'],
'E': ['RSS', 'DSI', 'CNM'],
'F': ['CNM', 'DSI', 'RSS']
}
choices = {
'DSI': ['B', 'E', 'C', 'D', 'A', 'F'],
'RSS': ['C', 'F', 'A', 'B', 'E', 'D'],
'CNM': ['A', 'D', 'B', 'C', 'E', 'F']
}
rss = 2
cnm = 1
dsi = 2
nbr_of_speciality = 3
results = []
students_with_out_choice = []
for student in students:
students_with_out_choice.append(student)
while len(students_with_out_choice) > 0:
for student in students_with_out_choice:
for i in range(nbr_of_speciality):
choice = students[student][i]
if (choice == "DSI" and dsi != 0) or (choice == "RSS" and rss != 0) or (choice == "CNM" and cnm != 0):
results.append([student, choice])
students_with_out_choice.remove(student)
if choice == "DSI":
dsi -= 1
if choice == "RSS":
rss -= 1
if choice == "CNM":
cnm -= 1
break
else:
free_choice = [k for (k,v) in results if choice == v]
student_proposer = free_choice[0]
for k in free_choice :
if choices[choice].index(k) > choices[choice].index(student_proposer):
student_proposer = k
rating_of_propose_student = choices[choice].index(student_proposer)
rating_of_actuel_student = choices[choice].index(student)
if rating_of_propose_student > rating_of_actuel_student:
students_with_out_choice.remove(student)
results.remove([student_proposer, choice])
results.append([student, choice])
students_with_out_choice.append(student_proposer)
break
elif i==nbr_of_speciality-1 :
print(f"student non-oriented : {student}")
students_with_out_choice.remove(student)
break
print(results)
第二种解决方案：
students = {
'A': ['dsi', 'rss', 'cnm'],
'B': ['rss', 'dsi', 'cnm'],
'C': ['cnm', 'dsi', 'rss'],
'D': ['dsi', 'rss', 'cnm'],
'E': ['rss', 'dsi', 'cnm'],
'F': ['cnm', 'dsi', 'rss'],
}
choices = {
'dsi': ['B', 'E', 'C', 'D', 'A', 'F'],
'cnm': ['A', 'D', 'B', 'C', 'E', 'F'],
'rss': ['C', 'F', 'A', 'B', 'E', 'D'],
}
places = {
'cnm': 1,
'rss': 2,
'dsi': 2,
}
left_places = places
results = {}
students_with_out_choices = ['A', 'B', 'C', 'D', 'E', 'F']
choices_left = students
def list_of_student_with_out_a_choice_left_to_prpose(students_with_out_choices, choices_left):
results = []
for e in students_with_out_choices:
if len(choices_left[e]) > 0:
results.append(e)
return results
def last_choice_in_ranking(s, choices_left, results, choices):
students_with_out_choices = []
ranging_list = choices[choices_left[e][0]]
ranging_student_list = []
for key in results:
if results[key] == choices_left[e][0]:
students_with_out_choices.append(key)
for i in range(len(ranging_list)):
if ranging_list[i] in students_with_out_choices:
ranging_student_list.append(ranging_list[i])
if ranging_list.index(e) < ranging_list.index(ranging_student_list[-1]):
return ranging_student_list[-1]
return s
list_of_oriented_student = students_with_out_choices
while len(list_of_oriented_student) > 0:
e = list_of_oriented_student[0]
first_choice = choices_left[e][0]
if places[first_choice] > 0:
results[e] = first_choice
left_places[first_choice] -= 1
students_with_out_choices.remove(e)
elif len(choices_left[e]) > 0:
student_less_rank_than_e = last_choice_in_ranking(e, choices_left, results, choices)
if student_less_rank_than_e != e:
del results[student_less_rank_than_e]
results[e] = first_choice
students_with_out_choices.remove(e)
students_with_out_choices.append(student_less_rank_than_e)
choices_left[e].remove(choices_left[e][0])
list_of_oriented_student = list_of_student_with_out_a_choice_left_to_prpose(students_with_out_choices, choices_left)
print("results: ", results)
liste_of_student_non_oriented=[]
for key in students:
if key not in results:
liste_of_student_non_oriented.append(key)
print(f"students non-oriented : {liste_of_student_non_oriented}")
我想编写一个程序，根据学生的选择和专业范围，将学生引导到他们在大学的专业。
每个专业可以招收多个学生（本例cnm =1，dsi=2，rss=2），学生人数可以多于名额（本例一个学生不可以）一个地方，因为只有 5 个地方）。
程序运行没有问题但输出不正确。（我不知道为什么） . 此示例的输出应为 ((a,cnm),(c,rss),(b,dsi),(e,dsi),(f,rss))
我在 youtube (https://youtu.be/FhRf0j068ZA ,the source code https://github.com/Schachte/stable-matching-algorithm) 上找到了一个视频，其中有人解释并编写了稳定匹配问题的代码，我喜欢那个代码，所以我接受了它，并尝试对其进行编辑，以便它可以解决我的问题问题
如果有人能帮助我，我将不胜感激。
*****这是我的代码
students = {
'A': ['CNM', 'DSI', 'RSS'],
'B': ['CNM', 'DSI', 'RSS'],
'C': ['DSI', 'CNM', 'RSS'],
'D': ['DSI', 'RSS', 'CNM'],
'E': ['RSS', 'DSI', 'CNM'],
'F': ['RSS', 'CNM', 'DSI']
}
choices = {
'DSI': ['C', 'E','D', 'B','F','A'],
'RSS': ['B','F','A', 'E', 'D','C'],
'CNM': ['A', 'B','C', 'D','E','F']
}
rss=2
cnm = 1
dsi=2
results = []
students_with_out_choice =[]
for student in students:
students_with_out_choice.append(student)
while (len(students_with_out_choice) > 0 ):
for i in range (3):
for student in students_with_out_choice:
for choice in students[student]:
if ((choice == "DSI" and dsi != 0) or (choice == "RSS" and rss != 0) or (choice == "CNM" and cnm != 0)):
results.append([student, choice])
students_with_out_choice.remove(student)
if (choice == "DSI"):
dsi -= 1
if (choice == "RSS"):
rss -= 1
if (choice == "CNM"):
cnm -= 1
break
else:
for key, value in results:
if choice == value:
a= key
etudiant_actuel = choices[choice].index(a)
etudiant_proposer = choices[choice].index(student)
if (etudiant_actuel >etudiant_proposer):
students_with_out_choice.remove(student)
students_with_out_choice.append(a)
a = student
break
elif(i==2):
students_with_out_choice.remove(student)
break
print(results)
您的代码中的一个问题可能是您在迭代列表 (students_with_out_choice) 时更改了它。这通常会导致意想不到的结果。
正如@enke 所指出的，延迟接受算法是此处选择的方法。这个算法的实现在你的例子中看起来像这样：
s = {
'A': ['CNM', 'DSI', 'RSS'],
'B': ['CNM', 'DSI', 'RSS'],
'C': ['DSI', 'CNM', 'RSS'],
'D': ['DSI', 'RSS', 'CNM'],
'E': ['RSS', 'DSI', 'CNM'],
'F': ['RSS', 'CNM', 'DSI']
}
r = {
'DSI': ['C', 'E', 'D', 'B', 'F', 'A'],
'RSS': ['B', 'F', 'A', 'E', 'D', 'C'],
'CNM': ['A', 'B', 'C', 'D', 'E', 'F']
}
p = {
'DSI': 2,
'RSS': 2,
'CNM': 1
}
def get_matched_students(students, rankings, places):
waiting_students = [student for student in students]
matching_results = {choice: [] for choice in places}
def get_waiting_list_without_student(student):
return [x for x in waiting_students if x != student]
def get_sorted_results_with_student(student, choice):
matching_results[choice].append(student)
return [x for x in rankings[choice] if x in matching_results[choice]]
while waiting_students:
for student in waiting_students.copy():
if not students[student]:
waiting_students = get_waiting_list_without_student(student)
continue
choice = students[student].pop(0)
if len(matching_results[choice]) < places[choice]:
matching_results[choice] = get_sorted_results_with_student(student, choice)
waiting_students = get_waiting_list_without_student(student)
else:
if rankings[choice].index(student) < rankings[choice].index(matching_results[choice][-1]):
matching_results[choice] = get_sorted_results_with_student(student, choice)
waiting_students = get_waiting_list_without_student(student)
waiting_students.append(matching_results[choice].pop())
return matching_results
print(get_matched_students(s, r, p))
这将为您提供与每个科目匹配的学生列表：{'DSI': ['C', 'E'], 'RSS': ['B', 'F'], 'CNM': ['A']}
如果你想从学生的角度来看结果，你可以这样做：
results = get_matched_students(s, r, p)
results_by_students = [[student, course] for student in s for course, result in results.items() if student in result]
print(results_by_students)
# Output: [['A', 'CNM'], ['B', 'RSS'], ['C', 'DSI'], ['E', 'DSI'], ['F', 'RSS']]
我最终使用两种不同的解决方案解决了我的问题。
第一个解决方案是在我的第一个程序中发现了错误并进行了更正。
students = {
'A': ['DSI', 'RSS', 'CNM'],
'B': ['RSS', 'DSI', 'CNM'],
'C': ['CNM', 'DSI', 'RSS'],
'D': ['DSI', 'RSS', 'CNM'],
'E': ['RSS', 'DSI', 'CNM'],
'F': ['CNM', 'DSI', 'RSS']
}
choices = {
'DSI': ['B', 'E', 'C', 'D', 'A', 'F'],
'RSS': ['C', 'F', 'A', 'B', 'E', 'D'],
'CNM': ['A', 'D', 'B', 'C', 'E', 'F']
}
rss = 2
cnm = 1
dsi = 2
nbr_of_speciality = 3
results = []
students_with_out_choice = []
for student in students:
students_with_out_choice.append(student)
while len(students_with_out_choice) > 0:
for student in students_with_out_choice:
for i in range(nbr_of_speciality):
choice = students[student][i]
if (choice == "DSI" and dsi != 0) or (choice == "RSS" and rss != 0) or (choice == "CNM" and cnm != 0):
results.append([student, choice])
students_with_out_choice.remove(student)
if choice == "DSI":
dsi -= 1
if choice == "RSS":
rss -= 1
if choice == "CNM":
cnm -= 1
break
else:
free_choice = [k for (k,v) in results if choice == v]
student_proposer = free_choice[0]
for k in free_choice :
if choices[choice].index(k) > choices[choice].index(student_proposer):
student_proposer = k
rating_of_propose_student = choices[choice].index(student_proposer)
rating_of_actuel_student = choices[choice].index(student)
if rating_of_propose_student > rating_of_actuel_student:
students_with_out_choice.remove(student)
results.remove([student_proposer, choice])
results.append([student, choice])
students_with_out_choice.append(student_proposer)
break
elif i==nbr_of_speciality-1 :
print(f"student non-oriented : {student}")
students_with_out_choice.remove(student)
break
print(results)
第二种解决方案：
students = {
'A': ['dsi', 'rss', 'cnm'],
'B': ['rss', 'dsi', 'cnm'],
'C': ['cnm', 'dsi', 'rss'],
'D': ['dsi', 'rss', 'cnm'],
'E': ['rss', 'dsi', 'cnm'],
'F': ['cnm', 'dsi', 'rss'],
}
choices = {
'dsi': ['B', 'E', 'C', 'D', 'A', 'F'],
'cnm': ['A', 'D', 'B', 'C', 'E', 'F'],
'rss': ['C', 'F', 'A', 'B', 'E', 'D'],
}
places = {
'cnm': 1,
'rss': 2,
'dsi': 2,
}
left_places = places
results = {}
students_with_out_choices = ['A', 'B', 'C', 'D', 'E', 'F']
choices_left = students
def list_of_student_with_out_a_choice_left_to_prpose(students_with_out_choices, choices_left):
results = []
for e in students_with_out_choices:
if len(choices_left[e]) > 0:
results.append(e)
return results
def last_choice_in_ranking(s, choices_left, results, choices):
students_with_out_choices = []
ranging_list = choices[choices_left[e][0]]
ranging_student_list = []
for key in results:
if results[key] == choices_left[e][0]:
students_with_out_choices.append(key)
for i in range(len(ranging_list)):
if ranging_list[i] in students_with_out_choices:
ranging_student_list.append(ranging_list[i])
if ranging_list.index(e) < ranging_list.index(ranging_student_list[-1]):
return ranging_student_list[-1]
return s
list_of_oriented_student = students_with_out_choices
while len(list_of_oriented_student) > 0:
e = list_of_oriented_student[0]
first_choice = choices_left[e][0]
if places[first_choice] > 0:
results[e] = first_choice
left_places[first_choice] -= 1
students_with_out_choices.remove(e)
elif len(choices_left[e]) > 0:
student_less_rank_than_e = last_choice_in_ranking(e, choices_left, results, choices)
if student_less_rank_than_e != e:
del results[student_less_rank_than_e]
results[e] = first_choice
students_with_out_choices.remove(e)
students_with_out_choices.append(student_less_rank_than_e)
choices_left[e].remove(choices_left[e][0])
list_of_oriented_student = list_of_student_with_out_a_choice_left_to_prpose(students_with_out_choices, choices_left)
print("results: ", results)
liste_of_student_non_oriented=[]
for key in students:
if key not in results:
liste_of_student_non_oriented.append(key)
print(f"students non-oriented : {liste_of_student_non_oriented}")