/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Find all stable matchings (stable marriages) by exhaustive search. Written Jan. 17th 2007 by Markus Triska (triska@metalevel.at) Public domain code. Tested with Scryer Prolog. Note that there are much more efficient algorithms for this task! See for example the Gale-Shapley algorithm, available from: https://www.metalevel.at/misc/galeshapley.pl ============================================ - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */ :- use_module(library(pairs)). :- use_module(library(clpz)). :- use_module(library(lists)). :- use_module(library(dif)). man_preferences(a, "edcba"). man_preferences(b, "aedcb"). man_preferences(c, "baedc"). man_preferences(d, "cbaed"). man_preferences(e, "dcbae"). woman_preferences(a, "abcde"). woman_preferences(b, "bcdea"). woman_preferences(c, "cdeab"). woman_preferences(d, "deabc"). woman_preferences(e, "eabcd"). %?- stable_marriage(M). %@ M = [a-a,b-b,c-c,d-d,e-e] %@ ; M = [a-e,b-a,c-b,d-c,e-d] %@ ; false. stable_marriage(Pairs) :- Ms0 = "abcde", permutation(Ms0, Ms), pairs_keys_values(Pairs, Ms0, Ms), \+ unstable_marriage(Pairs). unstable_marriage(Pairs) :- member(Man-Woman, Pairs), woman_index(Woman, Man, WI), dif(Man1, Man), member(Man1-Woman1, Pairs), man_index(Man1, Woman1, MI1), man_index(Man1, Woman, MI2), MI2 #< MI1, woman_index(Woman, Man1, WI1), WI1 #< WI. man_index(Man, Woman, I) :- man_preferences(Man, Ps), once(nth0(I, Ps, Woman)). woman_index(Woman, Man, I) :- woman_preferences(Woman, Ps), once(nth0(I, Ps, Man)).