#OK to post
#Rebecca Embar, 1-27-2022, Homework 11

read `C11.txt`:

#2
GaleShTW:=proc(M,W) local GS:
	GS:=GaleShT(W,M):
	inv(GS[1]),GS[2]:
end:

#3
CheckOpt:=proc(M,W) local GSM,GSW,i:
	GSM := GaleShT(M,W)[1]:
	GSW := GaleShTW(M,W)[1]:
	
	for i from 1 to nops(GSM) do
		if M[i][GSM[i]] > M[i][GSW[i]] then
			return false:
		fi:
		if W[i][inv(GSM)[i]] < W[i][inv(GSW)[i]] then
			return false:
		fi:
	end:
	true:
end:

#4
#Takes as input lists of lists of partial preferences, M and W,
#where M[i][j] = 0 if Mr. i would rather be single than marry Ms. j
#and W[j][i] = 0 if Ms. j would rather be single than marry Mr. i
#If stable matching exists, returns that stable matching
#If no stable matching exists, returns false

GaleShP:=proc(M,W) local n,i,j,Mnew,Wnew,matching:
	n := nops(M):
	
	#Introduce dummy man and woman
	Mnew := [op(M),[seq(i,i=1..n+1)]]:
	Wnew := [op(W),[seq(i,i=1..n+1)]]:
	
	#Add dummy man and woman to list of preferences
	Mnew := [seq([op(Mnew[i]),max(Mnew[i])+1],i=1..n),Mnew[n+1]]:
	Wnew := [seq([op(Wnew[i]),max(Wnew[i])+1],i=1..n),Wnew[n+1]]:
	
	#Rewrite preferences to remove 0s
	for i from 1 to n do
		for j from 1 to n do
			if Mnew[i][j] = 0 then 
				Mnew[i][j] := max(Mnew[i])+1:
			fi:
			if Wnew[i][j] = 0 then
				Wnew[i][j] := max(Wnew[i])+1:
			fi:
		od:
	od:
	
	#Run GS algorithm and check stability
	matching := GaleShT(Mnew,Wnew)[1]:
	if matching[n+1] = n+1 then
		return [seq(matching[i],i=1..n)]:
	fi:
	false:
end: