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)
Advertisement
Answer
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']]