Array-only implementation of Gale-Shapley

gale_shapley.c

#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.

gale_shapley.py

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