Skip to content

Instantly share code, notes, and snippets.

@skiano
Created April 12, 2017 21:32
Show Gist options
  • Save skiano/d1a9990873a7b1b60989d196228c0d37 to your computer and use it in GitHub Desktop.
Save skiano/d1a9990873a7b1b60989d196228c0d37 to your computer and use it in GitHub Desktop.
Thinking about stable matching within a homogeneous group based on similarity
const diff = (a, b) => Math.abs(a - b);
const removeSelf = (items, self) => (id) => items[id] !== items[self];
const makeComparator = (items, target) => (a, b) =>
diff(items[target], items[b]) - diff(items[target], items[a]);
const getStableMatches = (items) => {
const matches = [];
const available = [...items.keys()];
const preferences = available.map(id =>
available.filter(removeSelf(items, id)).sort(makeComparator(items, id)));
let c = 0;
function getMatch(id) {
const preferred = preferences[id].pop();
const reciprocalPreferences = preferences[preferred];
const reciprocalPreference = reciprocalPreferences.length > 0 ?
reciprocalPreferences[reciprocalPreferences.length - 1] : id;
if (available.includes(preferred) && id === reciprocalPreference) {
// remove both and make a match
available.splice(available.indexOf(id), 1);
available.splice(available.indexOf(reciprocalPreference), 1);
matches.push([id, preferred]);
// find the next match if there are more than 2 things to match
if (available.length >= 2) getMatch(available[0])
} else {
// find a more equitable match
getMatch(preferred);
}
c += 1;
}
getMatch(0);
console.log(`Total attempts: ${c}`)
return matches;
}
function getRandomInt(min, max) {
return Math.floor(Math.random() * (max - min + 1)) + min;
}
const items = Array.from(new Array(8 * 2)).map(() => getRandomInt(0, 1000))
console.log(`
Items: ${items}
Total items: ${items.length}
`)
const matches = getStableMatches(items);
console.log(`
Matches: ${JSON.stringify(matches)}
`)
@skiano
Copy link
Author

skiano commented Apr 12, 2017

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment