Skip to content

Instantly share code, notes, and snippets.

@dato
Last active March 10, 2017 01:05
Show Gist options
  • Save dato/30d3dea336d1a171e6a6293088bac19f to your computer and use it in GitHub Desktop.
Save dato/30d3dea336d1a171e6a6293088bac19f to your computer and use it in GitHub Desktop.
Array-only implementation of Gale-Shapley
#include <stdlib.h>
int *gale_shapley(int **P, int **R, int n) {
/*
* proposers[propidx] is the next proposer without
* assigned reviwer. Loop ends when propidx hits -1.
*/
int propidx = n - 1; // proposers acts as a stack.
int *proposers = malloc(n * sizeof(*proposers));
/*
* prop_wish[p] is the index of p’s next candidate
* in p’s preference row. Initialized to 0.
*/
int *prop_wish = calloc(n, sizeof(*prop_wish));
/*
* rev_is_with[r] is the final assignment for reviewer
* r. This is also the return value of the function.
*/
int *rev_is_with = malloc(n * sizeof(*rev_is_with));
for (int i = 0; i < n; i++) {
proposers[i] = i; // 0 to n-1, i.e. all
rev_is_with[i] = -1; // No initial assignments.
}
/*
* Finally, rev_pref[r][p] is how high is p in r’s scale.
* Lower is better, i.e. if r’s preferred candidate is X,
* rev_pref[r][X] is 0.
*/
int **rev_pref = malloc(n * sizeof(*rev_pref));
for (int i = 0; i < n; i++) {
// Allocate memory and initialize.
rev_pref[i] = malloc(n * sizeof(**rev_pref));
for (int j = 0; j < n; j++)
rev_pref[i][R[i][j]] = j;
}
while (propidx >= 0) {
int prop = proposers[propidx];
int rev = P[prop][prop_wish[prop]++];
int rival = rev_is_with[rev];
if (rival < 0) {
rev_is_with[rev] = prop;
propidx--; // prop is matched for now.
}
else if (rev_pref[rev][prop] < rev_pref[rev][rival]) {
rev_is_with[rev] = prop;
proposers[propidx] = rival; // rival becomes unmatched.
}
// Else, the loop will choose the same proposer again, with
// their next preferred candidate.
}
return rev_is_with;
}
// TODO: input format so as not to need lookup tables in main().
//
// TL;DR: a format a-la-Pajek which lists all strings first, and
// uses index-based lists for data.
def gale_shapley(P, R):
## See comments in C version ##
n = len(P)
proposers = list(range(n))
prop_wish = [0] * n
rev_is_with = [None] * n
rev_pref = [dict(p, pos) for pos, p in enumerate(R[i])
for i in range(n)]
while proposers:
p = proposers[-1]
rev = P[p][prop_wish[p]]
rival = rev_is_with[rev]
if rival is None:
rev_is_with[rev] = p
proposers.pop()
elif rev_pref[rev][p] < rev_pref[rev][rival]:
rev_is_with[rev] = p
proposers[-1] = rival
prop_wish[p] += 1
return rev_is_with
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment