
%\noindent \textbf{Stable Marriage (Pair Matching)}
\subsection{Stable Marriage (Pair Matching)}

Problem: Find matching between group of men and women such that
no pair of people would rather be in a different pair.

Basic idea:
\small
\begin{lstlisting}
Put all men onto a free list #1
while (no change)
  foreach m on free list #1
    order all women according to m's preference
    foreach w on m's pref. list
     if w is not engaged
       engage (m, w)
       change = true
     if w is engaged to m'
       if w prefers m to m'
         put m' on free list #2
         engage (m, w)
         change = true
    endfor
    if m was not matched
       put m on free list #2
  endfor
  swap free list #2 and #1
end while
\end{lstlisting}
\normalsize

If the number of men equals the number of women, all
men will be matched.  If there's more men than women,
free list \#1 will have the list of unmatched men.

%Example code

\lstset{language=C++}
\begin{lstlisting}
#include "prelude.cpp"
#include <list>
#include <deque>

using namespace std;

// Assumptions: men and women are both
// identified by integers, starting from 0
typedef int manid;
typedef int womanid;

struct man {
    int id; int people; int minutes;
    man(int i, int p, int m):
      id(i), people(p), minutes(m) {}
};

struct woman {
    int id; int seats; int minutes;
    woman(int i, int p, int m):
        id(i), seats(p), minutes(m) {}
};

vector<man> men;
vector<woman> women;

// representation of fit between man/woman
typedef pair<int,int> score;
// how much does a given man like this woman?
typedef pair<score, womanid> prefPair;

score calc_score(man m, woman w) {
    // (extraseats, extraminutes)
    return score(w.seats - m.people,
                  w.minutes - m.minutes);
}

bool sortPrefList(const prefPair& a,
                   const prefPair& b) {
    return a.first < b.first;
}

void stable_marriage(vector<man>& M,
                     vector<woman>& W) {
 // initially all men are free
 deque<man> q(ALL(M));

 map<womanid, bool> womantaken;
 map<manid, bool> mantaken;
 map<womanid, manid> husband;
 map<manid, list<prefPair> > prefs;

 FOR(i,M.size()) {
   prefs[i] = list<prefPair>();
   FOR(j,W.size()) {
    score s = calc_score(M[i], W[j]);
    // are the given man and woman
    //   even potentially compatible?
    // Not if the man is bigger than the woman
    if(s.first >= 0 && s.second >= 0) {
      prefs[i].push_back( prefPair(s, j) );
    }
   }
   prefs[i].sort(sortPrefList);
 }

 while(!q.empty()) {
   man aMan = q.front();
   q.pop_front();

   manid m = aMan.id;

   // if the man has "proposed"
   //   to every woman, he's SOL
   if(prefs[m].empty()) { continue; }

   // Pick the highest-ranked woman
   //   left for the man
   prefPair scorepair = prefs[m].front();
   prefs[m].pop_front();

   womanid w = scorepair.second;

   // if woman is free, "engage" m and the woman
  if(!womantaken[w]) {
    womantaken[w] = true;
    mantaken[m] = true;
    husband[w] = m;
  } else {
    // w is currently engaged to another man, m2
    manid m2 = husband[w];
    score s1 = calc_score(M[m],  W[w]);
    score s2 = calc_score(M[m2], W[w]);
    if(s1 < s2) {
      // m is better match than m2
      husband[w] = m;
      mantaken[m] = true;

      // m2 returns to the dating pool
      q.push_back(M[m2]);
      mantaken[m2] = false;
    } else { // m is still free
      q.push_back(aMan);
    }
  }
 }

 // by now, all women have taken the man
 //    that fits them best.
 int bachelors = 0;
 int people_in_tents = 0;
 FOR(i,M.size()) {
   if(!mantaken[i]) {
     bachelors++;
     people_in_tents += men[i].people;
   }
 }
 printf("%2d %d\n", bachelors,
        people_in_tents);
}

int main(void) {
 int p, d, s, h, m, w, r;
 int casenumber = 0;
 while(true) {
   w = 0;
   cin >> w;
   if(w == 0) return 0;

   ++casenumber;
   men.clear();
   women.clear();

   FOR(i,w) {
     cin >> p >> d;
     men.push_back(man(i,p,d));
   }

   cin >> r;
   string line;
   getline(cin, line); // discard endline
   FOR(i,r) {
     getline(cin, line);
     string::size_type c = line.find(':', 0);
     if(c != string::npos) line[c] = ' ';
        stringstream ss(line);
        ss >> s >> h >> m;
        m += 60 * (h - 14);
        women.push_back(woman(i,s,m));
     }
     cout << "Trial " << casenumber  << ": ";
     stable_marriage(men, women);
  }
}

\end{lstlisting}
\normalsize

%\noindent \textbf{End Stable Marriage (Pair Matching)}

%%% Local Variables:
%%% mode: latex
%%% TeX-master: "../ref-doc"
%%% End:
