12
\$\begingroup\$

I've written a solution for the stable marriage problem in the case that the number of men is not equal to the number of women. My problem is not that I can't prove my code is right. The problem is I don't know the complexity of my algorithm. I've put some descriptions in the execution so that it becomes easy to understand what the algorithm does.

Extended Stable Marriage Problem:

Assume that we have \$m\$ men and \$w\$ women. Each man gives a list of his preferences between women. Also, Each woman gives a list of her preferences between men. Assume that \$m\$ is greater than \$w\$. (I mean the number of men is more than the number of women) The objective is to find an stable matching. This stable matching should have some properties :

  1. It's obvious that we can't find a match for all of the men. So, some of them will be alone after the execution of the algorithm. But, The point is, if for example \$m\$ is alone, there shouldn't be a woman like \$w\$ such that \$w\$ prefers to be with \$m\$, but she is with someone else.

  2. For each \$(m,w)\$ and \$(m',w')\$ as two pairs of our stable matching, we say \$(m,w')\$ is an unstable pair if \$m\$ likes \$w'\$ more than \$w\$, and also \$w'\$ likes \$m\$, more than \$m'\$. This stable matching that the algorithm should provide, should not contain any unstable pairs.

My way of solving the problem:

I said I can apply Gale-Shapley algorithm first. Then, I check if a man is alone, but hasn't proposed to all women. If there exists such a man, I say this man should propose to other women in his preference list (which he hasn't proposed yet). I repeat this procedure till all of the men are engaged or if a man like \$m\$ is alone, \$m\$ has proposed to all women and is rejected by all of them.

men_prefer_list = [
    [2, 3, 1],
    [3, 1, 2],
    [2, 3, 1],
    [1, 2, 3],
    [1, 3, 2]
]
women_prefer_list = [
    [1, 2, 3, 4, 5],
    [2, 3, 4, 5, 1],
    [4, 5, 1, 2, 3]

]
proposals_counter = []
men_engaged = []
women_engaged = []
for i in range(len(men_prefer_list)):
    proposals_counter.append(0)
for i in range(len(men_prefer_list)):
    men_engaged.append(0)
for i in range(len(women_prefer_list)):
    women_engaged.append(0)


def inverse_arr(arr):
    temp_arr = arr[:]
    arr_inverse = []
    for k in range(len(temp_arr)):
        arr_inverse.append(0)
    for k in range(len(temp_arr)):
        arr_inverse[temp_arr[k]-1] = k+1
    return arr_inverse

#######################################################################################################################
# FIRST ITERATION - BEGIN                                                                                             #
#######################################################################################################################

for i in range(len(men_prefer_list)):
    print "Trying to find a good partner for Man #", i+1
    for j in range(len(women_prefer_list)):
        if women_engaged[men_prefer_list[i][j]-1] == 0:
            print "Man #", i+1, "likes to be with Woman #", men_prefer_list[i][j]
            print "Woman #", men_prefer_list[i][j], " isn\'t engaged to anybody.\nSo Man #", i+1, \
                " became engaged with Woman #", men_prefer_list[i][j]
            proposals_counter[i] += 1
            men_engaged[i] = men_prefer_list[i][j]
            women_engaged[men_prefer_list[i][j]-1] = i+1
            break
        else:
            print "Man #", i+1, "likes Woman #", men_prefer_list[i][j]
            print "But Woman #", men_prefer_list[i][j], " is already engaged."
            proposals_counter[i] += 1
            woman = men_prefer_list[i][j]
            fiance = women_engaged[men_prefer_list[i][j]-1]
            new_proposer = i+1
            accepted = 0
            temp=women_prefer_list[men_prefer_list[i][j]-1]
            temp2=temp[:]
            inverse = inverse_arr(temp2)
            print "Woman #", men_prefer_list[i][j], " has to choose between Man #", i+1, " and Man #", fiance
            print "Here is the list of Woman #", men_prefer_list[i][j], "\'s preferences"
            print women_prefer_list[men_prefer_list[i][j]-1]
            print "And here is the inverse list corresponding to it"
            print inverse
            print "i = ", i, "-", "inverse[i] is : ", inverse[i], "fiance = ", fiance, " - and inverse[fiance] is : ", inverse[fiance]
            if inverse[i] < inverse[fiance-1]:
                print "Woman #", men_prefer_list[i][j], "prefers to be with Man #", i+1
                accepted = 1
            if accepted == 1:
                men_engaged[fiance-1] = 0
                women_engaged[woman-1] = new_proposer
                men_engaged[new_proposer-1] = woman
                break
            else:
                print "Woman #", men_prefer_list[i][j], "prefers to be with Man #", fiance
                print "So, The proposal was rejected!"
                continue


#######################################################################################################################
# FIRST ITERATION - END                                                                                               #
#######################################################################################################################
print "First iteration was finished... The results : "
print "Men Engaged: ", men_engaged
print "Women Engaged: ", women_engaged
print "Number of proposals: ", proposals_counter
#######################################################################################################################
# DO THEY REALLY DESERVE TO BE ALONE? - BEGIN                                                                         #
#######################################################################################################################
def some_man_is_alone_but_hasnt_proposed_to_all_women():
    result = []
    for i in range(len(men_engaged)):
        if men_engaged[i] == 0:
            if proposals_counter[i] < len(women_engaged):
                result.append(True)
                result.append(i)
                return result
    result.append(False)
    result.append(-1)
    return result

condition = some_man_is_alone_but_hasnt_proposed_to_all_women()
while True in condition:
    the_man = some_man_is_alone_but_hasnt_proposed_to_all_women()
    the_man = the_man[1]
    the_first_woman_he_hasnt_proposed_yet = proposals_counter[the_man]
    the_mans_prefer_list = men_prefer_list[the_man]
    i = the_man
    print "It turns out Man #", i+1, "is alone and hasn\'t proposed to all women."
    for j in range(the_first_woman_he_hasnt_proposed_yet, len(the_mans_prefer_list)):
        print "Man #", i+1, "likes Woman #", men_prefer_list[i][j]
        print "But Woman #", men_prefer_list[i][j], " is already engaged."
        proposals_counter[i] += 1
        woman = men_prefer_list[i][j]
        fiance = women_engaged[men_prefer_list[i][j]-1]
        new_proposer = i+1
        accepted = 0
        temp = women_prefer_list[men_prefer_list[i][j]-1]
        temp2 = temp[:]
        inverse = inverse_arr(temp2)
        print "Woman #", men_prefer_list[i][j], " has to choose between Man #", i+1, " and Man #", fiance
        print "Here is the list of Woman #", men_prefer_list[i][j], "\'s preferences"
        print women_prefer_list[men_prefer_list[i][j]-1]
        print "And here is the inverse list corresponding to it"
        print inverse
        print "i = ", i, "-", "inverse[i] is : ", inverse[i], "fiance = ", fiance, " - and inverse[fiance] is : ", inverse[fiance-1]
        if inverse[i] < inverse[fiance-1]:
            print "Woman #", men_prefer_list[i][j], "prefers to be with Man #", i+1
            accepted = 1
        if accepted == 1:
            men_engaged[fiance-1] = 0
            women_engaged[woman-1] = new_proposer
            men_engaged[new_proposer-1] = woman
            break
        else:
            print "Woman #", men_prefer_list[i][j], "prefers to be with Man #", fiance
            print "So, The proposal was rejected!"
            continue
    condition = some_man_is_alone_but_hasnt_proposed_to_all_women()


#######################################################################################################################
# DO THEY REALLY DESERVE TO BE ALONE? - END                                                                           #
#######################################################################################################################

print "The final result: "
print "Men engaged: ", men_engaged
print "Women engaged: ", women_engaged
print "Number of proposals: ", proposals_counter

So, what is the complexity of line 104 to 140 (the while True in condition: … loop)? I asked some of my friends but they didn't know either. Can I make it even better?

The code can also be found on GitHub.

\$\endgroup\$
  • 5
    \$\begingroup\$ Welcome to CR! For those of us that don't know what the stable marriage problem is, can you please edit your question to include a description of it, so reviewers can refer to the specs instead of inferring them from your implementation? \$\endgroup\$ – Mathieu Guindon Feb 16 '17 at 20:45
  • \$\begingroup\$ @Mat'sMug Sure! I'll write it :) it takes time but i'll do that in the next minutes :) \$\endgroup\$ – Arman Malekzadeh Feb 16 '17 at 20:47
  • \$\begingroup\$ @Mat'sMug how about it now? is it good sir? :) \$\endgroup\$ – Arman Malekzadeh Feb 16 '17 at 20:54
  • 4
    \$\begingroup\$ Excellent, thanks! Note that reviewers are free to comment on any/all aspects of your code. Also... "line 104 to 140" is a bit hard to tell without the line numbers (the function's name would be better IMO), and while reviewers can definitely assess the complexity of your solution since you voiced it as a concern, it's possible (even likely) that they don't specifically focus on these lines - "can I make it even better" will definitely be addressed in all reviews. I hope you get great reviews! \$\endgroup\$ – Mathieu Guindon Feb 16 '17 at 21:02
  • 1
    \$\begingroup\$ for i in range(len... isn't pythonic. In Python, you should iterate over the contents of a sequence directly. \$\endgroup\$ – MKesper Feb 17 '17 at 7:53
5
\$\begingroup\$

This post is form a long time ago, but I scrolled past it, and I think it could use some improvements. I will try to stay in since that is what you used.

Review

  1. men_prefer_list = [[2, 3, 1],
                      [3, 1, 2],
                      [2, 3, 1],
                      [1, 2, 3],
                      [1, 3, 2]]
    

    Globals should be named, GLOBALS. All caps is the standard way to write global variables.

  2. proposals_counter = []
    men_engaged = []
    women_engaged = []
    for i in range(len(men_prefer_list)):
        proposals_counter.append(0)
    for i in range(len(men_prefer_list)):
        men_engaged.append(0)
    for i in range(len(women_prefer_list)):
        women_engaged.append(0)
    

    Variables should be as close to the scope as possible. When you modify globals somewhere in your program it might become really hard to track that 1 bug.

  3. You could use list comprehension to declare those variables in one line like this:

    proposals_counter = [0 for _ in men_prefer_list]
    
  4. When using list comprehension and you don't need the variable, it is Python idiom to write _ instead.

  5. def inverse_arr(arr):
        temp_arr = arr[:]
        arr_inverse = []
        for k in range(len(temp_arr)):
            arr_inverse.append(0)
        for k in range(len(temp_arr)):
           arr_inverse[temp_arr[k]-1] = k+1
        return arr_inverse
    

    You don't need to copy the variable, since you do not change the original list. That temp var is not needed.

  6. This could also use some list comprehension, with proposed changes that becomes:

    def inverse_arr(arr):
        arr_inverse = [0 for _ in arr]
        for k in range(len(arr)):
           arr_inverse[arr[k]-1] = k+1
        return arr_inverse
    
  7. for i in range(len(men_prefer_list)):
    

    Use enumerate; see the relevant PEP article.

  8. print "Trying to find a good partner for Man #", i+1
    

    Use parenthesis with the print () statements, this will make your code work in .

  9. You could use some formatting to make the string concatenations a bit nicer looking:

    print ("Trying to find a good partner for Man #{0}".format(i+1))
    
  10. temp=women_prefer_list[men_prefer_list[i][j]-1]
    temp2=temp[:]
    inverse = inverse_arr(temp2)
    

    Why all these temp variables? They are never used, and since the original list is not altered. It makes no sense to use a temp variable. Just write:

    inverse = inverse_arr(women_prefer_list[men_prefer_list[i][j]-1])
    
  11. def some_man_is_alone_but_hasnt_proposed_to_all_women():
        result = []
        for i in range(len(men_engaged)):
            if men_engaged[i] == 0:
                if proposals_counter[i] < len(women_engaged):
                    result.append(True)
                    result.append(i)
                    return result
        result.append(False)
        result.append(-1)
        return result
    

    Again use list comprehension; you can use conditionals in list comprehension, which makes this code block almost a one-liner.

  12. Naming is tough, but some_man_is_alone_but_hasnt_proposed_to_all_women() seems waaay too long a name; maybe rename it to men_all_proposed() ?

    return [i for i,e in enumerate(men_engaged) if proposals_counter[i] < len(women_engaged) and not men_engaged[i]]
    

    This would change the logic a bit, as the list will be empty if all men proposed to all woman, but since empty lists are considered falsey in Python you could check like this:

    if not men_all_proposed()
    

    BUT I think if you put this conditional before your FIRST ITERATION block, this would be one loop, because after this conditional you kinda repeat yourself a lot.

    def marriage(preferred_men, preferred_women):
        proposed = [
                        { woman: False for woman in range(len(preferred_women)) }
                        for man in preferred_men
                   ]
        engaged_men=[ None for _ in preferred_men ]
        engaged_woman=[ None for _ in preferred_women ]
    
        while not all(v for man in proposed for v in man.values()):
            for man in range(len(engaged_men)):
                for woman in preferred_men[man]:
                    if not engaged_men[man] is None:
                        break
                    if not proposed[man][woman]:
                        if engaged_woman[woman] is None:
                            engaged_men[man] = woman
                            engaged_woman[woman] = man
                        else:
                            if preferred_women[woman].index(engaged_woman[woman]) > preferred_women[woman].index(man):
                                engaged_men[engaged_woman[woman]] = None
                                engaged_woman[woman] = man
                                engaged_men[man] = woman
    
                        proposed[man][woman] = True
    
        return engaged_men, engaged_woman
    
    if __name__ == '__main__':
        preferred_men = [[1, 2, 0],
                         [2, 0, 1],
                         [1, 2, 0],
                         [0, 1, 2],
                         [0, 2, 1]]
    
        preferred_women = [[0, 1, 2, 3, 4],
                           [1, 2, 3, 4, 0],
                           [3, 4, 0, 1, 2]]
    
        print(marriage(preferred_men, preferred_women))
    
\$\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.