Stable marriage problem
Jörg Oliver Pinn
does anybody have an implementation of the stable marriage algorithm in
prolog or who has a good link for me where I can find a few tips?
Joerg
Colin Barker
This is how I solved it. I have omitted married/3 and prefers/3 so as to
leave you something to do :-)
/* solve(Men, Women, Marriages) is true if Marriages is a set of stable
*/
/* marriages between the Men and the Women.
*/
/* e.g. solve([a,b,c,d,e], [p,q,r,s,t], Marriages).
*/
solve(Men, Women, Marriages):-
generate(Men, Women, Marriages),
test(Men, Women, Marriages).
/* generate(Men, Women, Marriages) is true if Marriages is a set of
*/
/* possible marriages between the Men and the Women.
*/
generate([], [], []).
generate([Man|Men], Women, [m(Man,Woman)|Marriages]):-
select(Woman, Women, Women1),
generate(Men, Women1, Marriages).
/* test(Men, Women, Marriages) is true if Marriages is a set of stable
*/
/* marriages between the Men and the Women.
*/
test([], _, _).
test([Man|Men], Women, Marriages):-
test_1(Women, Man, Marriages),
test(Men, Women, Marriages).
test_1([], _, _).
test_1([Woman|Women], Man, Marriages):-
not(unstable(Man, Woman, Marriages)),
test_1(Women, Man, Marriages).
/* unstable(Man, Woman, Marriages) is true if the Man and the Woman both
*/
/* prefer each other to their spouses as defined by the set of
Marriages.*/
unstable(Man, Woman, Marriages):-
married(Man, Wife, Marriages),
married(Husband, Woman, Marriages),
prefers(Man, Woman, Wife),
prefers(Woman, Man, Husband).
/* select(X, Ys, Zs) is true if Zs is the result of removing one
*/
/* occurrence of the element X from the list Ys.
*/
select(X, [X|Ys], Ys).
select(X, [Y|Ys], [Y|Zs]):-select(X, Ys, Zs).
/* married(Man, Woman, Marriages) is true if the Man and the Woman are *
/
/* married as defined by the set of Marriages.
*/
/* prefers(Person, OtherPerson, Spouse) is true if the Person prefers the
*/
/* OtherPerson to his Spouse.
*/
/* preferences(Person, List) is true if the Person prefers people of the
*/
/* other sex in the order given in the List.
*/
preferences(a, [q,t,p,r,s]). preferences(p, [e,a,d,b,c]).
preferences(b, [p,q,r,s,t]). preferences(q, [d,e,b,a,c]).
preferences(c, [q,r,t,s,p]). preferences(r, [a,d,b,c,e]).
preferences(d, [p,r,q,s,t]). preferences(s, [c,b,d,a,e]).
preferences(e, [t,r,q,p,s]). preferences(t, [d,b,c,e,a]).
Colin
E-mail: mailto:colin....@wanadoo.fr
Internet: http://perso.wanadoo.fr/colin.barker
Andrzej Lewandowski
<colin....@wanadoo.fr> wrote:
>Jörg Oliver Pinn a écrit dans le message <3857CEA7...@gmd.de>...
>>Hi,
>>
>>does anybody have an implementation of the stable marriage algorithm in
>>prolog or who has a good link for me where I can find a few tips?
>>
>>Joerg
>
>This is how I solved it. I have omitted married/3 and prefers/3 so as to
>leave you something to do :-)
>
>/* solve(Men, Women, Marriages) is true if Marriages is a set of stable
>*/
Mr. Barker, for this homework I give you just B-. Program is not too
elegant. I must say however that for other homework problems that you
kindly solved for students posting on this group you deserve at least
B+
A.L.