Extended stable marriage challenge

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 :



-
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.

-
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_counte

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 python-2.x since that is what you used.

Review

-

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.

-

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.

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

proposals_counter = [0 for _ in men_prefer_list]

-
When using list comprehension and you don't need the variable, it is Python idiom to write _ instead.

-

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.

-
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

-

for i in range(len(men_prefer_list)):

Use enumerate; see the relevant PEP article.

-

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

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

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

-

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

-

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.

-
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,

StackExchange Code Review Q#155547, answer score: 5