Help:=proc(): print(`BP(n,K)`): print(`AP(F,M),AP2(F,M,b,ForB,ForG)`): end: with(combinat): BP:=proc(n,K) local p,i,S: S:={}: for i from 1 to K do p:=randperm(n): S:=S union {seq([i,p[i]],i=1..n)}: od: S: end: #Boys(F): set of boys in F Boys:=proc(F) local i: {seq(F[i][1],i=1..nops(F) ) }: end: #Girls(F): set of girls in F Girls:=proc(F) local i: {seq(F[i][2],i=1..nops(F) ) }: end: #AP(F,M): Alternating path #with friendships F and marriages M AP:=proc(F,M) local Sb,i,P: Sb:=Boys(F) minus Boys(M): for i from 1 to nops(Sb) do P:=AP1(F,M,Sb[i]): if P<>FAIL then RETURN(P): fi: od: FAIL: end: #GirlFriends(F,b): the set of #girl-friends of boy b in Friendship F GirlFriends:=proc(F,b) local S,i: S:={}: for i from 1 to nops(F) do if F[i][1]=b then S:=S union {F[i][2]}: fi: od: S: end: #BoyFriends(F,g): the set of #boy-friends of girl g in Friendship F BoyFriends:=proc(F,g) local S,i: S:={}: for i from 1 to nops(F) do if F[i][2]=g then S:=S union {F[i][1]}: fi: od: S: end: #AP1(F,M,b): an alternating path #in Friendships F, Marriages M, #starting at a boy b AP1:=proc(F,M,b) AP2(F,M,b,{},{}): end: #AP2(F,M,b,ForB,ForG): #an aleternating path that starts at #b and avoids the boys of ForB and #the girls of ForG AP2:=proc(F,M,b,ForB,ForG) local Gfb,SGfb,g,i,b1,P: Gfb:=GirlFriends(F,b) minus ForG: SGfb:=Gfb minus Girls(M): if SGfb<>{} then RETURN([b,SGfb[1] ]): fi: for i from 1 to nops(Gfb) do g:=Gfb[i]: b1:=BoyFriends(M,g)[1]: P:=AP2(F,M,b1,ForB union {b,b1},ForG union {g}): if P<>FAIL then RETURN([b,g,op(P)]): fi: od: FAIL: end: #Marry(F): inputs a set of friendships and #outputs a maximal matching using the #alternating path algorithm Marry:=proc(F) local M,P,i: M:={}: P:=AP(F,M): while P<>FAIL do M:=M minus {seq([P[2*i+1],P[2*i]],i=1..nops(P)/2-1)} union {seq([P[2*i-1],P[2*i]],i=1..nops(P)/2)}: P:=AP(F,M): od: M: end: