0
$\begingroup$

I was reading this thread The stable marriage algorithm with asymmetric arrays and started to solve the problem asked in this thread about matching 5 students with 10 dorms.

One of the answer suggested to add 5 dummy students to make number of students equal to 10.

Lets suppose before adding the dummy students the preferences are below -:

s1 - d3 d9 d2 d7 d1 d10 d4 d6 d8 d5

s2 - d8 d2 d3 d5 d10 d4 d7 d1 d9 d6

s3 - d2 d9 d1 d8 d4 d3 d10 d6 d5 d7

s4 - d9 d6 d2 d5 d8 d1 d3 d7 d4 d10

s5 - d10 d2 d5 d4 d3 d7 d9 d8 d6 d1

d1 - s1 s5 s3 s4 s2

d2 - s2 s3 s1 s5 s4

d3 - s3 s5 s4 s1 s2

d4 - s3 s5 s4 s2 s1

d5 - s2 s5 s3 s1 s4

d6 - s3 s4 s5 s1 s2

d7 - s2 s4 s5 s1 s3

d8 - s3 s5 s1 s4 s2

d9 - s2 s5 s3 s1 s4

d10 - s5 s2 s1 s3 s4

How should I go about this after adding the dummy students. My approach is below -: I am putting 5 dummy student in lower preference for dorms and giving random dorms preference to dummy students. Dummy students are denoted by ds.

s1 - d3 d9 d2 d7 d1 d10 d4 d6 d8 d5

s2 - d8 d2 d3 d5 d10 d4 d7 d1 d9 d6

s3 - d2 d9 d1 d8 d4 d3 d10 d6 d5 d7

s4 - d9 d6 d2 d5 d8 d1 d3 d7 d4 d10

s5 - d10 d2 d5 d4 d3 d7 d9 d8 d6 d1

ds1 - d6 d2 d9 d10 d4 d5 d3 d1 d8 d7

ds2 - d4 d2 d6 d3 d10 d9 d5 d7 d1 d8

ds3 - d7 d3 d5 d1 d10 d9 d2 d8 d4 d6

ds4 - d2 d8 d1 d10 d6 d3 d4 d5 d9 d7

ds5 - d10 d2 d6 d3 d4 d5 d1 d7 d9 d8

d1 - s1 s5 s3 s4 s2 ds1 ds2 ds3 ds4 ds5

d2 - s2 s3 s1 s5 s4 ds1 ds2 ds3 ds4 ds5

d3 - s3 s5 s4 s1 s2 ds1 ds2 ds3 ds4 ds5

d4 - s3 s5 s4 s2 s1 ds1 ds2 ds3 ds4 ds5

d5 - s2 s5 s3 s1 s4 ds1 ds2 ds3 ds4 ds5

d6 - s3 s4 s5 s1 s2 ds1 ds2 ds3 ds4 ds5

d7 - s2 s4 s5 s1 s3 ds1 ds2 ds3 ds4 ds5

d8 - s3 s5 s1 s4 s2 ds1 ds2 ds3 ds4 ds5

d9 - s2 s5 s3 s1 s4 ds1 ds2 ds3 ds4 ds5

d10 - s5 s2 s1 s3 s4 ds1 ds2 ds3 ds4 ds5

If i solve the above with gale shapley will I get the right results?? In other words, will I get the stable matching?

$\endgroup$
  • $\begingroup$ Welcome to Computer Science! If the original problem comes from an online course or article, please add a URL in the question. If it comes from a book or a paper, a reference. Besides paying proper attribute to the original source, all that information motivates and helps more people answer your question faster and better. $\endgroup$ – Apass.Jack Oct 31 '18 at 17:32
  • $\begingroup$ We would expect that you have tried solving that stable matching problem with dummy students added before your raised the question. Please tell us your result. It is helpful for your development and it will save time for all readers. $\endgroup$ – Apass.Jack Oct 31 '18 at 17:33
0
$\begingroup$

This will give you a stable matching when you will use the Gale Shapley algorithm. You can use the below code. a and b are dictionaries in the code

def insert_dummies(a,b):
  length_a=len(a.keys())
  length_b=len(b.keys())
  items_a=list(a.keys())
  items_b=list(b.keys())
  dummy_list=[]
  if length_a>length_b:
    dummy_number=length_a-length_b
    nummer=1
    while nummer<dummy_number+1:
        dummy_list.append("Dummy%d" %nummer)
        nummer=nummer+1
    for i in items_a:
      f=0
      while dummy_number>f:
        a.setdefault(i,[]).append(dummy_list[f])
        f=f+1
    n=0    
    while n<(dummy_number):
      for z in dummy_list:
        b[z]=items_a
        n=n+1
  if length_a<length_b:
    dummy_number=length_b-length_a
    nummer=1
    while nummer<dummy_number+1:
        dummy_list.append("Dummy%d" %nummer)
        nummer=nummer+1
    for i in items_b:
      f=0
      while dummy_number>f:
        b.setdefault(i,[]).append(dummy_list[f])
        f=f+1
    n=0    
    while n<(dummy_number):
      for z in dummy_list:
        a[z]=items_b
        n=n+1
    else:
        return

  return a,b



#This function returns the result of the algorithm. Parameter 'a' refers to the preferences of the gender
#that we want to find the optimized solution for, while the parameter 'b' refers to the preferences of the other gender.
def StableMatching(a, b):
    #this function returns a stable matching
    dict_a = a.keys()  #This list contains the names of the group for we are optimizing.
    names1 = list(dict_a)
    dict_b = b.keys() #This list contains the names of the other group.
    names2 = list(dict_b)
    i = 0
    engaged = []
    #This dictionary contains the names of the gender for which we attempt to find the optimized solution.
    times = {}
    t = 0
    position_existing = 0
    position_potential = 0
    counter = 0
    #Can have the values 'free' or 'not free'.
    a_p = {}
    while(counter < len(names1)):
        a_p.update({names1[counter]: 'free'})
        counter = counter + 1

    counter = 0
    #Can have the values 'free' or 'not free'.
    b_p = {}
    while(counter < len(names2)):
        b_p.update({names2[counter]: 'free'})
        counter = counter + 1

    counter = 0
    #Initialization of times dictionary.
    while(counter < len(names1)):
        times.update({names1[counter]: 0})
        counter = counter + 1

    #The value -1 has the meaning that when all men or women are paired, the loop stops;
    while((i != -1) and (a_p[names1[i]] == 'free') and (times[names1[i]] < len(names2))):
        #The man/woman who is next in the ranking of the proposals.
        w = a[names1[i]][times[names1[i]]]
        if(b_p[w] == 'free'):
            a_p[names1[i]] = 'not free'
            b_p[w] = 'not free'
            t = (names1[i], w)
            engaged.append(t)
            times[names1[i]] = times[names1[i]] + 1
        else:
            q = 0
            while(q < (len(engaged))):
                  if(w in engaged[q]):
                      t1 = engaged[q]
                      l = 0
                      while(l < len(names1)):
                          if(names1[i] == b[w][l]):
                              position_potential = l
                              l = len(names1)
                          l = l + 1
                      l = 0
                      while(l < len(names1)):
                          if(t1[0] == b[w][l]):
                              position_existing = l
                              l = len(names1)
                          l = l + 1
                      if(position_potential < position_existing):
                          t = (names1[i], w)
                          engaged.append(t)
                          del(engaged[q])
                          a_p[names1[i]] = 'not free'
                          a_p[t1[0]] = 'free'
                          q = len(engaged)
                  q = q + 1

            times[names1[i]] = times[names1[i]] + 1
        i = i + 1
        #If the variable i has passed from all the men/women then it starts from the beginning
        #in order to check the ones who remain single.
        if(i == len(names1)):
            i = 0
        if(a_p[names1[i]] == 'not free'):
            k = 0
            z = False
            while((k < len(names1)) and (z == False)):
                if(a_p[names1[k]] == 'free'):
                    i = k
                    z = True
                k = k + 1
            if((k == len(names1)) and (z == False)):
                i = -1
    engaged_dict = dict(engaged)
    return engaged_dict
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.