I have two questions about stable marriage problem.
Given n men and n women, where each person has ranked all members of the opposite sex with an unique number between 1 and n in order of preference, marry the men and women together such that there are no two people of opposite sex who would both rather have each other than their current partners. If there are no such people, all the marriages are "stable".
I know the solution from http://en.wikipedia.org/wiki/Stable_marriage_problem. The wiki page explains the solution, but it doesn't explain how this solution was inducted.
Q1: Can anyone explain to me how to think of this kind of paring problem? So for similar problems I can have a way of thinking.
Q2: What if we want all possible stable marriage combinations?
Here is a paper that claims to give an algorithm to enumerate all stable marriages in optimal time and space. The author Dan Gusield is a very reputable computer scientist so it's almost certainly correct.