I want to write a program that oriented student to their specialty in university depending on their choices and their range in the specialty.
each specialty can take multiple student (in this case cnm =1 , dsi=2 , rss=2),and the number of student can be more than the number of places (in this case one student not gonna have a place because there is only 5 places ).
The program run with out a problem but the output is not correct .(and I couldn’t know why ) . The output for this example should be ((a,cnm),(c,rss),(b,dsi),(e,dsi),(f,rss))
i found a video on youtube (https://youtu.be/FhRf0j068ZA ,the source code https://github.com/Schachte/stable-matching-algorithm) where the person explain and write a code for stable matching problem , i liked that code so i toke it and i tried to edited so it can be solve my problem
If anyone could help me out I would really appreciate it.
*****this is my code
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)
One problem in your code could be that you are changing a list (students_with_out_choice) while iterating over it. This often leads to unexpected results.
As @enke has pointed out, the deferred acceptance algorithm is the method of choice here. An implementation of this algorithm could look something like this with your example:
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))
This will give you the lists of students that have been matched to each subject: {'DSI': ['C', 'E'], 'RSS': ['B', 'F'], 'CNM': ['A']}
If you want to see the results from the student's perspective, you can do something like this:
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']]