Gale–Shapley algorithm for Stable marriage problem

gs-example01.js

#!/usr/bin/env node

/**
 * Gale–Shapley algorithm for Stable marriage problem
 *
 * https://en.wikipedia.org/wiki/Stable_marriage_problem
 * http://toyokeizai.net/articles/-/11584
 */
'use strict'

const shuffle = require('shuffle-array')

function defineMembers (memberCount = 10) {
  const men = shuffle(new Array(memberCount).fill(null).map((_, i) => ({
    name: `man#${i}`,
    rejectedBy: [],
    likes: []
  })))
  const women = shuffle(new Array(memberCount).fill(null).map((_, i) => ({
    name: `woman#${i}`,
    proposedBy: [],
    keeps: null,
    likes: []
  })))

  for (const m of men) {
    m.likes = shuffle(women).map(({name}) => name)
  }

  for (const w of women) {
    w.likes = shuffle(men).map(({name}) => name)
  }

  return {men, women}
}

const memberCount = 10
const {men, women} = defineMembers(memberCount)

const menByName = Object.assign({}, ...men.map((man) => ({
  [man.name]: man
})))
const womenByName = Object.assign({}, ...women.map((woman) => ({
  [woman.name]: woman
})))

for (let round = 0; round < 4; round++) {
  for (const m of men) {
    const isKept = women.some(({keeps}) => keeps === m.name)
    if (!isKept) {
      const best = m.likes.find((name) => !m.rejectedBy.includes(name))
      if (best) {
        womenByName[best].proposedBy.push(m.name)
      }
    }
  }
  for (const w of women) {
    const [best, ...notGoodEnough] = w.proposedBy.sort((a, b) =>
      w.likes.indexOf(a) - w.likes.indexOf(b)
    )
    w.keeps = best || null
    for (const n of notGoodEnough) {
      menByName[n].rejectedBy.push(w.name)
    }
  }
}

{
  const couples = women
    .map(({name, keeps}) => keeps ? [name, keeps] : null)
    .filter(Boolean)
    .map(([wName, mName]) => [
      womenByName[wName],
      menByName[mName]
    ])

  const successCount = couples.length
  const failureCount = memberCount - successCount
  console.log(`${successCount} success, ${failureCount} failure`)
  console.log(
    couples.map(([w, m]) => [
      w.name, w.likes.indexOf(m.name), m.name, m.likes.indexOf(w.name)
    ])
  )

}