StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>The Gale-Shapley algorithm (for the Stable Marriage problem) applies only when each person has a ranked list of all other participants -- you may or may not be able to convert your problem to that form (make everyone rank <em>everyone</em>). </p> <p>Also, note that the thing it is optimizing for is something different: it tries to find a set of <strong>stable marriages</strong>, where no pair of people will "elope" because they prefer each other to their current partners. This is not something you care about in your Secret Santa application. </p> <p>What you want (depending on your definition of "best") is a <strong>maximum-weight bipartite matching</strong>, which fixes both the above objections: put the "givers" on one side, the "receivers" on the other (so two copies of each person, in this case), give each edge a weight corresponding to how highly that giver ranks that receiver, and it is now the <a href="http://en.wikipedia.org/wiki/Assignment_problem" rel="noreferrer">assignment problem</a>. You can use the <a href="http://en.wikipedia.org/wiki/Hungarian_algorithm" rel="noreferrer">Hungarian algorithm</a> for this, or simpler (slower) ones. You can also vary how you assign the weights to optimize for different things (e.g. maximize the number of people who get their first choice, or minimize the worst choice that anyone gets, etc.)</p> <p>If you do use the Gale-Shapley stable marriage algorithm, note that it is optimal for the "proposers" (male-optimal and female-pessimal), so be sure to put the "givers" as the "proposers", and not vice versa.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload