-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathNRMP_method.py
113 lines (95 loc) · 5.81 KB
/
NRMP_method.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
# -*- coding: utf-8 -*-
"""
Created on Tue Sep 6 19:32:38 2022
@author: wsycx
"""
'''
assuming that:
1, every doctor ranks every hospital in their preference list
2, every hospital ranks every perspective doctors in their preference list
3, input of the doctors perference is in the format of (doctors*hospitals)
4, input of the hospital perference is in the format of (hospitals*doctors)
5, the output is in the format of #hospitals lists of list containing the admission result
'''
import math
import numpy as np
######################################################################################################
# Algorithm design #
######################################################################################################
'''
This is a method that checks if there is a higher ranking doctor in the hospital's tentative acceptence list
input:
Doctor_Id: the doctor id of the new coming doctor
Hospital_Id: the new coming doctor's choise of hospital
output:
status:
0: there is an replaced doctor
-1: there is no replaced doctor
-2: the exisitng doctors in the hospital target list all rank higher than the new coming doctor
'''
# check if there's a higher ranked docter in the hospital target list
# Doctor Id and Hospital Id must start from 1
def higher_ranker_check(Doctor_Id, Hospital_Id, Hospital_target_list, Hospital_Rank, Hospital_cap, Doctor_is_occupied_list):
# if the list is empty or have avalible space add the doctor in the target list
if len(Hospital_target_list[Hospital_Id - 1]) == 0 or len(Hospital_target_list[Hospital_Id -1 ]) < Hospital_cap:
Hospital_target_list[Hospital_Id -1 ].append(Doctor_Id)
Doctor_is_occupied_list[Doctor_Id-1] = True # set the docters status as occupied
return -1 # -1 means there's no replaced doctor in record
else:
# if the hospital list is full
replaceble_doctor_list = []
replaceble_doctor_Id = None
# finding the replaceble doctor's ID
for doctor_ID_in_hospital_list in Hospital_target_list[Hospital_Id -1 ]:
# if an exisiting doctor in the list ranks shorter than the new coming doctor, the existing doctor will be move to the replaceble list
if Hospital_Rank[Hospital_Id -1 ].index(doctor_ID_in_hospital_list) > Hospital_Rank[Hospital_Id-1].index(Doctor_Id):
#replaceble_doctor_Id = doctor_ID_in_hospital_list
# if the replacable_doctor_list is empty and the replaceble doctor's ID
if len(replaceble_doctor_list) == 0:
replaceble_doctor_Id = doctor_ID_in_hospital_list
replaceble_doctor_list.append(replaceble_doctor_Id)
else:
# find the shortest ranking replaceble doctor
if Hospital_Rank[Hospital_Id -1 ].index(doctor_ID_in_hospital_list) > Hospital_Rank[Hospital_Id -1 ].index(replaceble_doctor_Id):
replaceble_doctor_Id = doctor_ID_in_hospital_list
replaceble_doctor_list[0] = replaceble_doctor_Id
# if there is a replaceble doctor in the hospital's target list
if replaceble_doctor_Id is not None:
Hospital_target_list[Hospital_Id -1 ].remove(replaceble_doctor_Id) # remove the replaced docter ID from the target list
Doctor_is_occupied_list[replaceble_doctor_Id-1] =False # set the replaced doctor status as available
Hospital_target_list[Hospital_Id -1].append(Doctor_Id) # add the new doctor's ID in the list
Doctor_is_occupied_list[Doctor_Id-1] = True # set the docters status as occupied
return 0 # 0 indicates there are replaced doctor in the record
else:
return -2 # -2 indicates that the exisitng doctors in the hospital target list all rank higher than the new coming doctor
'''
This is the main running function that runs the algorithm
input:
1, Doctor_is_occupied_list: a list of the occupation status for each doctor
Ture: this doctor has been reserved by certain hospital
False: this doctor has no hospital reserved him/her yet
2, num_doctor: number of perspective doctor
3, Doctor_Rank: a list for each doctor's hospital perfrence ranking
4, Hospital_target_list: Hospital's tentative acceptance list
output:
1, Hopital_final_list: Hospital's final acceptance list
'''
def run(Doctor_is_occupied_list, num_doctor, Hospital_cap, Doctor_Rank, Hospital_target_list,Hospital_Rank):
while all(Doctor_is_occupied_list) == False:
for i in range(num_doctor):
if Doctor_is_occupied_list[i] == False:
Doctor_Id = i+1
Doctor_Hospital_choice = Doctor_Rank[i][0]
status = higher_ranker_check(Doctor_Id, Doctor_Hospital_choice, Hospital_target_list,Hospital_Rank,Hospital_cap, Doctor_is_occupied_list)
del Doctor_Rank[i][0] # remove it's perfernece once submitted
# if the submission is rejected by the hosipital and the doctor still has a perfernece, try the next perference hoispital
while status == -2 and len(Doctor_Rank[i]) !=0:
Doctor_Hospital_choice = Doctor_Rank[i][0]
status = higher_ranker_check(Doctor_Id, Doctor_Hospital_choice, Hospital_target_list,Hospital_Rank,Hospital_cap, Doctor_is_occupied_list)
del Doctor_Rank[i][0] #remove it's perfernece once submitted
if status == -2 and len(Doctor_Rank[i])==0:
Doctor_is_occupied_list[i] = None
for i in range(len(Hospital_target_list)):
print('Hospital #: ' + str(i+1) + ' accepted doctor list is: ')
print(Hospital_target_list[i])
return Hospital_target_list