stable match algorithm for different sizes groups and limited places

Question

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)

Answer 1

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']]

Answer 2

I eventually resolved my problem using two different solutions.

the first soltion is that found the bugs in my first program and i corrected it.

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)

the seconde solution :

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}")