smp

15 Reputation

2 Badges

12 years, 299 days

MaplePrimes Activity


These are answers submitted by smp

Thanks a lot guys, really grateful for the help. Unfortunately I'm not familiar with Matlab or Python. I've spent a lot of time looking at the problem which is very interesting. I've managed to compute some of the algortihm. I also found a previous post a few years ago relating to my question about the stable arriage problem, so I've adjusted my code to match the code used in that previous post which looks a little bit neater:

stableMatching:= proc(M,W)
 local n,i,j,k,c,d,g,Mm,Ww,s:
    g:=0:
    c:=0:
 with(ArrayTools):
    n:=max(Size(M)):
       Mm := Array(1..n): #stores the number of the woman the man is married to
       Ww := Array(1..n):
         for i from 1 to n do #sets marriages to 0
         Mm[i] := 0:
         Ww[i] := 0:
        end do:
     for d from 1 while g<>n do #loops until all men are married
     for j from 1 to n do
     for i from 1 to n do
      if Ww(M[i,n-j+1])=0 then #if the man's prefered woman isn't married
        Mm[i]:= M[i,n-j+1]: #man marries woman
         Ww[Mm[i]]:=i: #woman marries man
           g:=g+1:
         else
       for k from 1 to n do # see if the woman prefers the new man to old. if she does, swap.
        if W[M[i,n-j+1],k]=Ww(M[i,n-j+1]) then if c<>2 then
         c:=1:
          s:=k:
       end if:
       end if:
      if W[M[i,n-j+1],k]=i then if c=1 then
       c:=2:
     end if:  
    end if:
   end do:
    if c = 2 then #if she prefers the second man swaps them.
     Mm[Ww[s]]:=0:
     Mm[i]:=M[i,n-j+1]:
     Ww[Mm[i]]:=i:
    end if:
   end if:
  end do:
 end do:
end do:
return Mm
end proc

 

As an example when I used the two matrices M and W, I got [0,3,2] which doesn't work.

M:=Array([[1,2,3],[3,2,1],[2,1,3]]):
W:=Array([[2,1,3],[3,1,2],[1,3,2]]):

 

I think the problem as people before found may be that the loop isn't working if the female rejects someone.  I would be greatly appreciative if someone could see the mistake I have made in the code or what to do to make it work? Thanks guys for all your help so far, just spent so much time trying to find the solution

Many Thanks

Claudio



 

 

 

 

 

 

 

 

 

However I occured the same problem as was mentioned by people before that

Page 1 of 1