/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   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)).